Permutations Using Backtracking — Deep Dive with Java Examples

package io.thecodeforge.algorithms;

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);
        }
    }
}

package io.thecodeforge.algorithms;

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));
    }
}

package io.thecodeforge.algorithms;

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).
 */
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.
            if (index > 0
                    && inputElements[index] == inputElements[index - 1]
                    && !isElementUsed[index - 1]) {
                continue;
            }

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

            backtrackUnique(inputElements, isElementUsed, currentPermutation, uniquePermutations);

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

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

        System.out.println("Unique permutations: " + result.size());
        for (List<Integer> permutation : result) {
            System.out.println(permutation);
        }
    }
}

package io.thecodeforge.algorithms;

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.
 */
public class PermutationWithConsumer {

    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) {
            onPermutationFound.accept(Arrays.copyOf(workingArray, workingArray.length));
            return;
        }

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

    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};
        int[] count = {0};
        streamPermutations(elements, perm -> count[0]++);
        System.out.println("Total permutations processed: " + count[0]);
    }
}