Pattern 11: Backtracking / Subsets

0. The Template (Copy-Paste Skeleton)

Every backtracking problem is choose → explore → un-choose. The only thing that varies is the loop’s start index and the pruning condition.

// TEMPLATE — THE UNIVERSAL BACKTRACKING SKELETON
void backtrack(int start, List<Integer> path, List<List<Integer>> out, int[] nums) {
    // 1. RECORD / BASE CASE
    out.add(new ArrayList<>(path));      // subsets: record EVERY node
    // permutations/combinations instead: if (path.size() == k) { out.add(new ArrayList<>(path)); return; }

    for (int i = start; i < nums.length; i++) {
        // 2. PRUNE (skip duplicates / invalid branches)
        if (i > start && nums[i] == nums[i - 1]) continue;   // requires a SORTED nums

        path.add(nums[i]);                        // 3. CHOOSE
        backtrack(i + 1, path, out, nums);        // 4. EXPLORE  (see the index table below)
        path.remove(path.size() - 1);             // 5. UN-CHOOSE — non-negotiable
    }
}

The recursion index is the whole pattern — memorise this table

Problem type	Next call	Effect
Subsets / Combinations (no reuse)	`backtrack(i + 1, ...)`	each element used at most once, order fixed
Combination Sum (unlimited reuse)	`backtrack(i, ...)`	may pick `nums[i]` again
Permutations (all orderings)	`backtrack(0, ...)` + a `boolean[] used`	every position considers every unused element
Combinations of size k	`backtrack(i + 1, ...)` + `if (path.size() == k) return;`	fixed-length only

// PERMUTATIONS variant — no start index, a `used[]` instead
void permute(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> out) {
    if (path.size() == nums.length) { out.add(new ArrayList<>(path)); return; }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;  // dedupe (sorted input)
        used[i] = true;  path.add(nums[i]);
        permute(nums, used, path, out);
        path.remove(path.size() - 1);  used[i] = false;             // UN-CHOOSE both
    }
}

// CONSTRAINT-BUILDING variant — Generate Parentheses (LC 22): prune with counters, no array
void gen(int open, int close, int n, StringBuilder sb, List<String> out) {
    if (sb.length() == 2 * n) { out.add(sb.toString()); return; }
    if (open  < n)     { sb.append('('); gen(open+1, close, n, sb, out); sb.deleteCharAt(sb.length()-1); }
    if (close < open)  { sb.append(')'); gen(open, close+1, n, sb, out); sb.deleteCharAt(sb.length()-1); }
}

The four rules

Always new ArrayList<>(path) when recording. Adding path itself stores a reference to a list you keep mutating — every result comes out identical. This is the classic bug.
Every CHOOSE needs an UN-CHOOSE. If you set two things (used[i] and path), undo both.
Sort before deduping. if (i > start && nums[i] == nums[i-1]) continue; only works on sorted input — it keeps the first of each run of equal values and skips the rest.
Prune early, not at the leaf. Checking if (remaining < 0) return; at the top beats generating a full invalid branch and rejecting it. Pruning is what turns TLE into AC.

Complexity — know these numbers

Problem	Count	Time
Subsets	2ⁿ	O(n · 2ⁿ) — the `n` is the copy into the result
Permutations	n!	O(n · n!)
Combinations C(n,k)	C(n,k)	O(k · C(n,k))
N-Queens	—	O(n!) with pruning

1. Pattern Identification & Logic

How to Identify (Interview Triggers)

“Find all combinations / permutations / subsets”
“Generate all valid configurations” (parentheses, N-Queens)
“Decision tree” where you choose to include or exclude
Input size is small (n <= 20 typically)
“Distinct arrangements” or “unique” results

The Algorithm (Pseudocode)

Subsets (Include/Exclude):

backtrack(index, currentSubset):
    result.add(copy of currentSubset)

    for i = index to n-1:
        currentSubset.add(nums[i])
        backtrack(i + 1, currentSubset)
        currentSubset.removeLast()     // BACKTRACK

Permutations (Swap-based):

backtrack(index):
    if index == n:
        result.add(copy of nums)
        return

    for i = index to n-1:
        swap(nums[index], nums[i])
        backtrack(index + 1)
        swap(nums[index], nums[i])     // BACKTRACK (undo)

The ‘Trick’ to Know

Subsets vs. Permutations vs. Combinations:
- Subsets: order doesn’t matter, no repetition → for i = start
- Permutations: order matters → swap or boolean visited array
- Combinations: order doesn’t matter, specific size k → prune when remaining < k
Handling duplicates: Sort the array first, then skip if (i > start && nums[i] == nums[i-1]).

2. Java Implementation (Brute Force vs. Optimal)

Example Problem: Subsets - LC 78

Iterative (Bit Manipulation) - O(n * 2^n)

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;

        for (int mask = 0; mask < (1 << n); mask++) {
            List<Integer> subset = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    subset.add(nums[i]);
                }
            }
            result.add(subset);
        }
        return result;
    }
}

Optimal: Backtracking - O(n * 2^n)

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] nums, int start, List<Integer> current, List<List<Integer>> result) {
        result.add(new ArrayList<>(current));

        for (int i = start; i < nums.length; i++) {
            current.add(nums[i]);
            backtrack(nums, i + 1, current, result);
            current.remove(current.size() - 1);
        }
    }
}

Java Architecture Insights

new ArrayList<>(current): CRITICAL. Without copying, every entry in result points to the same list object, which ends up empty after backtracking.
current.remove(current.size() - 1): O(1) removal from end. Don’t use current.remove(element) which is O(n) and removes by value.
Why ArrayList over LinkedList? Random access for the copy constructor. LinkedList would be O(n) for get(i).

3. Mental Model & Visualization

ASCII Diagram (nums = [1, 2, 3])

                     []
                /     |     \
             [1]     [2]    [3]
            /   \     |
         [1,2] [1,3] [2,3]
           |
        [1,2,3]

Decision tree: at each level, choose to add nums[i] or move to next.
Backtrack = remove last element after exploring that branch.

Result: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

Senior Mental Trigger

“Find ALL possibilities with small input = backtracking decision tree (add, recurse, undo).”

4. Curated Problem Lists

Commonly Asked (Bread & Butter)

#	Problem	Difficulty
LC 78	Subsets	Medium
LC 46	Permutations	Medium
LC 77	Combinations	Medium
LC 39	Combination Sum	Medium
LC 22	Generate Parentheses	Medium

FAANG ‘Aha!’ Level (Hard/Unintuitive)

#	Problem	Difficulty
LC 90	Subsets II (with duplicates)	Medium
LC 47	Permutations II (with duplicates)	Medium
LC 51	N-Queens	Hard
LC 79	Word Search	Medium
LC 131	Palindrome Partitioning	Medium
LC 37	Sudoku Solver	Hard

5. Time & Space Complexity Table

Problem Type	Time	Space	Notes
Subsets	O(n * 2^n)	O(n)	2^n subsets, each up to n long
Permutations	O(n * n!)	O(n)	n! permutations
Combinations	O(k * C(n,k))	O(k)	C(n,k) combinations of size k