Permutations Backtracking — 48GB Heap Blowup at N=12

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.
 *
 * Output order: lexicographic when input is sorted.
 *
 * Time:  O(N * N!) — N! permutations, O(N) copy at each leaf
 * Space: O(N)      — recursion depth + visited array + current path
 *                    (O(N * N!) if accumulating all results)
 */
public class PermutationDecisionTree {

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

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

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

        // BASE CASE: current permutation has all N elements
        if (currentPermutation.size() == inputElements.length) {
            // CRITICAL: copy the list, not the reference.
            // currentPermutation is mutated throughout backtracking.
            // Storing the reference means every entry in allPermutations
            // points to the same object — which ends up empty.
            allPermutations.add(new ArrayList<>(currentPermutation));
            return;
        }

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

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

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

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

            // --- UNCHOOSE (backtrack) ---
            // Restore state exactly as it was before this iteration.
            // The next iteration of the loop must see a clean slate.
            currentPermutation.remove(currentPermutation.size() - 1);
            isElementUsed[index] = false;
        }
    }

    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
        result.forEach(System.out::println);

        // Demonstrate the reference trap explicitly
        System.out.println("\n--- Reference Trap Demo ---");
        List<List<Integer>> trapResult = new ArrayList<>();
        boolean[] used = new boolean[elements.length];
        List<Integer> path = new ArrayList<>();
        // Uncomment the line below and comment the copy line in backtrack to see all empty lists:
        // trapResult.add(path) instead of new ArrayList<>(path)
        System.out.println("Always use new ArrayList<>(currentPermutation) at the base case.");
    }
}

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[] needed.
 * The fixed prefix grows by one per recursive level.
 * At each level, swap each remaining element into the current
 * position, recurse, then swap BACK to restore array state.
 *
 * Output order: NOT lexicographic — differs from visited-array approach.
 * Document this in any API where ordering matters.
 *
 * Time:  O(N * N!) — same asymptotic as visited-array
 * Space: O(N)      — only the recursion stack (no extra path list or boolean array)
 *                    plus O(N) per leaf for the array snapshot
 */
public class InPlaceSwapPermutation {

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

    private static void swapBacktrack(
            int[] workingArray,
            int startIndex,
            List<int[]> allPermutations) {

        // BASE CASE: startIndex reached the end — full array is one permutation
        if (startIndex == workingArray.length) {
            // Arrays are mutable — must copy, not store the reference
            allPermutations.add(Arrays.copyOf(workingArray, workingArray.length));
            return;
        }

        for (int candidate = startIndex; candidate < workingArray.length; candidate++) {

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

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

            // --- UNCHOOSE: restore to pre-swap state ---
            // Without this, subsequent loop iterations see a corrupted array.
            // This is the most commonly forgotten line in interview code.
            swap(workingArray, startIndex, candidate);
        }
    }

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

    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
        System.out.println("Note: order is NOT lexicographic (differs from visited-array approach)");
        for (int[] permutation : result) {
            System.out.println(Arrays.toString(permutation));
        }

        // Verify 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.HashSet;
import java.util.List;
import java.util.Set;

/**
 * Permutations with duplicate input elements — two approaches.
 *
 * Approach A (visited-array): sort input, skip adjacent duplicates
 *   with the !used[i-1] pruning condition.
 *
 * Approach B (in-place swap): use a per-level HashSet to track
 *   which values have already been placed at the current position.
 */
public class PermutationWithDuplicates {

    // --- Approach A: Visited-Array with Sort + Prune ---

    public static List<List<Integer>> generateUniquePermutations(int[] inputElements) {
        // Sort is REQUIRED — groups duplicates adjacently so adjacent-skip works
        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(\n            int[] inputElements,\n            boolean[] isElementUsed,\n            List<Integer> currentPermutation,\n            List<List<Integer>> uniquePermutations) {

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

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

            if (isElementUsed[index]) {
                continue;
            }

            // DUPLICATE PRUNING:
            // Skip if this element equals the previous one AND the previous
            // one is NOT currently in our active path.
            //
            // WHY !used[i-1] and not used[i-1]?
            // When used[i-1] is false: the previous duplicate is not in our current
            // path. We already explored (or will explore) a branch starting with
            // that element. Starting another branch with an identical element at
            // the same position generates the same subtree — skip it.
            //
            // When used[i-1] is true: the previous duplicate IS in our path at a
            // different position. The resulting permutation is genuinely different
            // from any already generated — do NOT skip it.
            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;
        }
    }

    // --- Approach B: In-Place Swap with Per-Level Set ---

    public static List<int[]> generateUniqueSwapPermutations(int[] inputArray) {
        List<int[]> result = new ArrayList<>();
        int[] working = Arrays.copyOf(inputArray, inputArray.length);
        swapBacktrackUnique(working, 0, result);
        return result;
    }

    private static void swapBacktrackUnique(
            int[] arr, int startIndex, List<int[]> result) {

        if (startIndex == arr.length) {
            result.add(Arrays.copyOf(arr, arr.length));
            return;
        }

        // Track which VALUES have already been placed at startIndex this call
        // Using values (not indices) because we care about semantic duplicates
        Set<Integer> placedAtThisLevel = new HashSet<>();

        for (int candidate = startIndex; candidate < arr.length; candidate++) {
            // Skip if this value has already been the fixed element at this level
            if (placedAtThisLevel.contains(arr[candidate])) {
                continue;
            }
            placedAtThisLevel.add(arr[candidate]);

            swap(arr, startIndex, candidate);
            swapBacktrackUnique(arr, startIndex + 1, result);
            swap(arr, 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[] withDuplicates = {1, 1, 2};

        System.out.println("=== Approach A: Visited-Array + Sort + Prune ===");
        List<List<Integer>> resultA = generateUniquePermutations(withDuplicates.clone());
        System.out.println("Unique permutations: " + resultA.size()); // 3!/2! = 3
        resultA.forEach(System.out::println);

        System.out.println("\n=== Approach B: In-Place Swap + Per-Level Set ===");
        List<int[]> resultB = generateUniqueSwapPermutations(withDuplicates.clone());
        System.out.println("Unique permutations: " + resultB.size()); // also 3
        resultB.stream().map(Arrays::toString).forEach(System.out::println);
    }
}

package io.thecodeforge.algorithms;

import java.util.Arrays;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.function.Consumer;

/**
 * Memory-efficient permutation streaming using a Consumer callback.
 *
 * Memory cost: O(N) regardless of N! — only current path and
 * recursion stack are live. No result list ever grows.
 *
 * Also demonstrates early-exit via AtomicBoolean flag.
 * Do NOT use exception-throwing for early exit — exceptions are
 * orders of magnitude slower and pollute stack traces.
 */
public class PermutationWithConsumer {

    /**
     * Stream all permutations to a consumer. Memory stays O(N).
     * Safe for N up to 12-13. Add input validation for production use.
     */
    public static void streamPermutations(int[] inputArray, Consumer<int[]> onPermutation) {
        if (inputArray.length > 12) {
            throw new IllegalArgumentException(
                "N=" + inputArray.length + " exceeds safe limit. " +
                "N=12 generates ~479M permutations. Use constraint search instead.");
        }
        int[] working = Arrays.copyOf(inputArray, inputArray.length);
        swapBacktrack(working, 0, onPermutation);
    }

    private static void swapBacktrack(
            int[] working, int startIndex, Consumer<int[]> onPermutation) {

        if (startIndex == working.length) {
            onPermutation.accept(Arrays.copyOf(working, working.length));
            return;
        }

        for (int candidate = startIndex; candidate < working.length; candidate++) {
            swap(working, startIndex, candidate);
            swapBacktrack(working, startIndex + 1, onPermutation);
            swap(working, startIndex, candidate);
        }
    }

    /**
     * Stream permutations with early exit support.
     * Returns true if a valid permutation was found, false if all were exhausted.
     *
     * The consumer returns true to continue, false to stop.
     * Uses AtomicBoolean flag — NOT exception throwing.
     */
    public static boolean streamUntilFound(\n            int[] inputArray,\n            java.util.function.Predicate<int[]> onPermutation) {

        int[] working = Arrays.copyOf(inputArray, inputArray.length);
        AtomicBoolean found = new AtomicBoolean(false);
        swapBacktrackWithExit(working, 0, onPermutation, found);
        return found.get();
    }

    private static void swapBacktrackWithExit(
            int[] working, int startIndex,
            java.util.function.Predicate<int[]> onPermutation,
            AtomicBoolean stopFlag) {\n\n        // Check the flag at every frame entry — stops recursion as early as possible\n        if (stopFlag.get()) return;\n\n        if (startIndex == working.length) {\n            boolean continueSearching = onPermutation.test(\n                Arrays.copyOf(working, working.length));\n            if (!continueSearching) {\n                stopFlag.set(true);\n            }
            return;
        }

        for (int candidate = startIndex; candidate < working.length; candidate++) {
            if (stopFlag.get()) return; // check before each branch
            swap(working, startIndex, candidate);
            swapBacktrackWithExit(working, startIndex + 1, onPermutation, stopFlag);
            swap(working, 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}; // 4! = 24
        int[] count = {0};

        System.out.println("=== Streaming all permutations (memory stays O(N)) ===");
        streamPermutations(elements, perm -> count[0]++);
        System.out.println("Total permutations processed: " + count[0]); // 24

        System.out.println("\n=== Early exit: find first permutation starting with 3 ===");
        boolean found = streamUntilFound(
            elements,
            perm -> {\n                if (perm[0] == 3) {\n                    System.out.println(\"Found: \" + Arrays.toString(perm));\n                    return false; // stop searching\n                }\n                return true; // continue\n            }\n        );\n        System.out.println(\"Search completed, found: \" + found);\n\n        System.out.println(\"\\n=== Input validation for N > 12 ===\");\n        try {\n            streamPermutations(new int[13], perm -> {});\n        } catch (IllegalArgumentException e) {\n            System.out.println(\"Caught: \" + e.getMessage());\n        }\n    }\n}",
        "output": "=== Streaming all permutations (memory stays O(N)) ===\nTotal permutations processed: 24\n\n=== Early exit: find first permutation starting with 3 ===\nFound: [3, 1, 2]\nSearch completed, found: true\n\n=== Input validation for N > 12 ===\nCaught: N=13 exceeds safe limit. N=12 generates ~479M permutations. Use constraint search instead."
      }

package io.thecodeforge.algorithms;

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

/**
 * Approach 3: Bitmask Backtracking
 *
 * Replaces boolean[] with an int bitmask.
 * Bit i = 1 means element i is in the current path.
 * Bit i = 0 means element i is available.
 *
 * Benefits over boolean[]:
 *   - No array allocation per level
 *   - Single AND/OR/NOT operations — single CPU instructions
 *   - Mask passed by value: undo step is automatic on return
 *   - Better cache locality — mask stays in a register
 *
 * Limit: N <= 31 for int, N <= 63 for long.
 *
 * Time:  O(N * N!) — same asymptotic as other approaches
 * Space: O(N)      — recursion stack only; bitmask is a scalar
 */
public class BitmaskPermutation {

    public static List<List<Integer>> generatePermutations(int[] inputElements) {
        if (inputElements.length > 31) {
            throw new IllegalArgumentException(
                "Bitmask approach requires N <= 31. Got N=" + inputElements.length);
        }
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        // Start with usedMask = 0: no elements in use
        backtrack(inputElements, 0, path, result);
        return result;
    }

    private static void backtrack(\n            int[] arr,\n            int usedMask,     // passed by value — automatic undo on return\n            List<Integer> path,\n            List<List<Integer>> result) {

        if (path.size() == arr.length) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            // Check if bit i is set — single AND instruction
            if ((usedMask & (1 << i)) != 0) {
                continue; // element i is already in the path
            }

            // CHOOSE: set bit i — single OR instruction
            // Pass the new mask down; caller's mask is unchanged on return
            path.add(arr[i]);
            backtrack(arr, usedMask | (1 << i), path, result);

            // UNCHOOSE: remove from path
            // No mask restoration needed — usedMask was passed by value
            path.remove(path.size() - 1);
        }
    }

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

        System.out.println("Total permutations: " + result.size());
        result.forEach(System.out::println);

        System.out.println("\n--- Bitmask behaviour walkthrough for N=3 ---");
        System.out.println("Initial mask  : 000 (no elements used)");
        System.out.println("After placing element 0: mask = 001");
        System.out.println("After placing element 2: mask = 101");
        System.out.println("After placing element 1: mask = 111 (all used — leaf reached)");
        System.out.println("On return from leaf: mask reverts to 101 automatically (pass-by-value)");

        System.out.println("\n--- Input validation for N > 31 ---");
        try {
            generatePermutations(new int[32]);
        } catch (IllegalArgumentException e) {
            System.out.println("Caught: " + e.getMessage());
        }
    }
}