Permutations Using Backtracking — Deep Dive with Java Examples

import java.util.ArrayList;
import java.util.List;

/**
 * Approach 1: Visited-Array Backtracking
 *
 * Uses a boolean[] to track which elements are already placed
 * in the current partial permutation. At each recursive call,
 * we iterate over all elements, skip used ones, place the next
 * available element, recurse, then UNDO the placement.
 *
 * Time:  O(N * N!) — N! permutations, O(N) to copy each one
 * Space: O(N)      — recursion depth + visited array + current path
 */
public class PermutationDecisionTree {

    public static List<List<Integer>> generatePermutations(int[] inputElements) {
        List<List<Integer>> allPermutations = new ArrayList<>();
        boolean[] isElementUsed = new boolean[inputElements.length]; // tracks which slots are occupied
        List<Integer> currentPermutation = new ArrayList<>();

        backtrack(inputElements, isElementUsed, currentPermutation, allPermutations);
        return allPermutations;
    }

    private static void backtrack(
            int[] inputElements,
            boolean[] isElementUsed,
            List<Integer> currentPermutation,
            List<List<Integer>> allPermutations) {

        // BASE CASE: current permutation has all N elements — it's complete
        if (currentPermutation.size() == inputElements.length) {
            // IMPORTANT: copy the list, not the reference!
            // If you add currentPermutation directly, all stored results
            // will point to the same list and reflect its final (empty) state.
            allPermutations.add(new ArrayList<>(currentPermutation));
            return;
        }

        // RECURSIVE CASE: try placing each unused element at the next position
        for (int index = 0; index < inputElements.length; index++) {

            if (isElementUsed[index]) {
                continue; // skip elements already in the current path
            }

            // --- CHOOSE ---
            isElementUsed[index] = true;                    // mark as used
            currentPermutation.add(inputElements[index]);   // place element

            // --- EXPLORE ---
            backtrack(inputElements, isElementUsed, currentPermutation, allPermutations);

            // --- UNCHOOSE (backtrack) ---
            // Remove the last element we added — restoring state for the next branch
            currentPermutation.remove(currentPermutation.size() - 1);
            isElementUsed[index] = false; // mark as available again
        }
    }

    public static void main(String[] args) {
        int[] elements = {1, 2, 3};
        List<List<Integer>> result = generatePermutations(elements);

        System.out.println("Total permutations: " + result.size()); // 3! = 6
        for (List<Integer> permutation : result) {
            System.out.println(permutation);
        }
    }
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Approach 2: In-Place Swap Backtracking
 *
 * Works directly on the input array. No visited[] array needed.
 * The 'fixed' prefix grows by one element per recursive level.
 * At each level, swap each remaining element into the current
 * position, recurse, then swap back to restore array state.
 *
 * Time:  O(N * N!) — same asymptotic complexity
 * Space: O(N)      — only the recursion stack depth (no extra path list)
 */
public class InPlaceSwapPermutation {

    public static List<int[]> generatePermutations(int[] inputArray) {
        List<int[]> allPermutations = new ArrayList<>();
        // Work on a copy so we don't mutate the caller's array
        int[] workingArray = Arrays.copyOf(inputArray, inputArray.length);
        swapBacktrack(workingArray, 0, allPermutations);
        return allPermutations;
    }

    /**
     * @param workingArray  the array being rearranged in place
     * @param startIndex    the current position we're filling (left partition boundary)
     * @param allPermutations accumulator for completed permutations
     */
    private static void swapBacktrack(
            int[] workingArray,
            int startIndex,
            List<int[]> allPermutations) {

        // BASE CASE: startIndex has reached the end — the full array is one permutation
        if (startIndex == workingArray.length) {
            // Snapshot the current state of the array (arrays are mutable — copy it!)
            allPermutations.add(Arrays.copyOf(workingArray, workingArray.length));
            return;
        }

        // Try placing each element from [startIndex .. end] at position startIndex
        for (int swapCandidate = startIndex; swapCandidate < workingArray.length; swapCandidate++) {

            // --- CHOOSE: bring swapCandidate into the fixed prefix ---
            swap(workingArray, startIndex, swapCandidate);

            // --- EXPLORE: fix startIndex, recurse on the rest ---
            swapBacktrack(workingArray, startIndex + 1, allPermutations);

            // --- UNCHOOSE: restore the array to its pre-swap state ---
            // Without this, subsequent iterations in this loop see a corrupted array.
            swap(workingArray, startIndex, swapCandidate);
        }
    }

    private static void swap(int[] array, int firstIndex, int secondIndex) {
        int temp = array[firstIndex];
        array[firstIndex] = array[secondIndex];
        array[secondIndex] = temp;
    }

    public static void main(String[] args) {
        int[] elements = {1, 2, 3};
        List<int[]> result = generatePermutations(elements);

        System.out.println("Total permutations: " + result.size()); // 3! = 6
        for (int[] permutation : result) {
            System.out.println(Arrays.toString(permutation));
        }

        // Demonstrate that the ORIGINAL array is unmodified
        System.out.println("Original array after call: " + Arrays.toString(elements));
    }
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Permutations with duplicate input elements.
 *
 * Key technique: sort the input first, then skip a candidate
 * if it equals the previous element AND the previous element
 * is NOT currently in the active path (isElementUsed[i-1] == false).
 *
 * Why this condition works:
 *   - If isElementUsed[i-1] is TRUE, the previous duplicate is
 *     on a DIFFERENT branch of the tree — they produce distinct paths.
 *   - If isElementUsed[i-1] is FALSE, we're at the same level and
 *     would produce an identical subtree — prune it.
 */
public class PermutationWithDuplicates {

    public static List<List<Integer>> generateUniquePermutations(int[] inputElements) {
        // Sorting is REQUIRED — it groups duplicates together so our
        // adjacent-skip logic works correctly.
        Arrays.sort(inputElements);

        List<List<Integer>> uniquePermutations = new ArrayList<>();
        boolean[] isElementUsed = new boolean[inputElements.length];
        List<Integer> currentPermutation = new ArrayList<>();

        backtrackUnique(inputElements, isElementUsed, currentPermutation, uniquePermutations);
        return uniquePermutations;
    }

    private static void backtrackUnique(
            int[] inputElements,
            boolean[] isElementUsed,
            List<Integer> currentPermutation,
            List<List<Integer>> uniquePermutations) {

        if (currentPermutation.size() == inputElements.length) {
            uniquePermutations.add(new ArrayList<>(currentPermutation));
            return;
        }

        for (int index = 0; index < inputElements.length; index++) {

            // Skip elements already placed in the current path
            if (isElementUsed[index]) {
                continue;
            }

            // DUPLICATE PRUNING: skip this element if it's identical to the
            // previous one AND the previous one is not currently in use.
            // This ensures each value is only chosen once per tree level.
            if (index > 0
                    && inputElements[index] == inputElements[index - 1]
                    && !isElementUsed[index - 1]) {
                continue; // prune: this subtree is identical to one we already explored
            }

            // --- CHOOSE ---
            isElementUsed[index] = true;
            currentPermutation.add(inputElements[index]);

            // --- EXPLORE ---
            backtrackUnique(inputElements, isElementUsed, currentPermutation, uniquePermutations);

            // --- UNCHOOSE ---
            currentPermutation.remove(currentPermutation.size() - 1);
            isElementUsed[index] = false;
        }
    }

    public static void main(String[] args) {
        // Input has two 1s — without pruning we'd get 6 permutations (with dupes)
        int[] elementsWithDuplicates = {1, 1, 2};
        List<List<Integer>> result = generateUniquePermutations(elementsWithDuplicates);

        System.out.println("Unique permutations of [1, 1, 2]: " + result.size()); // expect 3
        for (List<Integer> permutation : result) {
            System.out.println(permutation);
        }

        System.out.println();

        // Confirm distinct elements still work correctly
        int[] distinctElements = {1, 2, 3};
        List<List<Integer>> distinctResult = generateUniquePermutations(distinctElements);
        System.out.println("Permutations of [1, 2, 3]: " + distinctResult.size()); // expect 6
    }
}

import java.util.Arrays;
import java.util.function.Consumer;

/**
 * Memory-efficient permutation generator using a Consumer callback.
 *
 * Instead of accumulating all N! permutations in a list (which blows
 * up memory for N > 11), we call a callback at each leaf.
 * Memory stays O(N) for the working array + call stack.
 *
 * This is the pattern to use in production when:
 *   - N > 10
 *   - You're streaming results to a file, network, or further processing
 *   - You only need the FIRST permutation matching some condition
 */
public class PermutationWithConsumer {

    /**
     * Generates all permutations and delivers each one to the provided consumer.
     *
     * @param inputArray the elements to permute (will not be modified)
     * @param onPermutationFound called once per complete permutation
     */
    public static void streamPermutations(int[] inputArray, Consumer<int[]> onPermutationFound) {
        int[] workingArray = Arrays.copyOf(inputArray, inputArray.length);
        swapBacktrackWithConsumer(workingArray, 0, onPermutationFound);
    }

    private static void swapBacktrackWithConsumer(
            int[] workingArray,
            int startIndex,
            Consumer<int[]> onPermutationFound) {

        if (startIndex == workingArray.length) {
            // Deliver a copy — the consumer might store it; don't hand out our working array
            onPermutationFound.accept(Arrays.copyOf(workingArray, workingArray.length));
            return;
        }

        for (int candidate = startIndex; candidate < workingArray.length; candidate++) {
            swap(workingArray, startIndex, candidate);  // choose
            swapBacktrackWithConsumer(workingArray, startIndex + 1, onPermutationFound); // explore
            swap(workingArray, startIndex, candidate);  // unchoose
        }
    }

    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void main(String[] args) {
        int[] elements = {1, 2, 3, 4};

        // Example 1: count without storing
        int[] permutationCount = {0}; // array trick to mutate inside lambda
        streamPermutations(elements, perm -> permutationCount[0]++);
        System.out.println("Permutation count for N=4: " + permutationCount[0]); // 24

        // Example 2: find first permutation where sum of first two > 5
        System.out.println("\nFirst permutation where first two elements sum > 5:");
        boolean[] found = {false};
        streamPermutations(elements, perm -> {
            if (!found[0] && perm[0] + perm[1] > 5) {
                System.out.println(Arrays.toString(perm));
                found[0] = true;
                // Note: backtracking still runs to completion — for true early-exit,
                // you'd need an exception or a flag checked at every recursive level.
            }
        });

        // Example 3: show N! growth — illustrates why N > 12 is dangerous
        System.out.println("\nN! growth table:");
        long factorial = 1;
        for (int n = 1; n <= 13; n++) {
            factorial *= n;
            System.out.printf("N=%2d  permutations=%,d%n", n, factorial);
        }
    }
}