Backtracking Fundamentals: Permutations, Combinations, Subsets

Backtracking Framework

Backtracking explores every possible branch of a decision tree using Depth-First Search (DFS). When a branch violates the constraints, we "prune" it by returning and reverting our choices.

// Logic Framework
void backtrack(state, choices, currentPath) {
    if (isGoalMet) {
        result.add(new ArrayList<>(currentPath)); // Copy for persistence
        return;
    }
    
    for (choice : choices) {
        // 1. Choose
        currentPath.add(choice);
        
        // 2. Recurse (often with a smaller subset of choices)
        backtrack(state, remainingChoices, currentPath);
        
        // 3. Backtrack (Undo selection)
        currentPath.removeLast();
    }
}

1. Subsets (Power Sets)

Problem: Given an array of distinct integers, return all possible subsets.

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> path, List<List<Integer>> res) {
    // Every node in the recursion tree represents a valid subset
    res.add(new ArrayList<>(path));
    
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        // i + 1 ensures the same element is not chosen twice in a path
        backtrack(nums, i + 1, path, res);
        path.removeLast();
    }
}

Subsets II (With Duplicates)

Rule: To avoid duplicates like [1, 2] and [1, 2], sort the array and skip identical elements at the same recursion level.

// Call: Arrays.sort(nums); then backtrack...
if (i > start && nums[i] == nums[i-1]) continue; 

2. Combinations

Problem: Pick $k$ numbers from 1 to $n$.

public void backtrack(int n, int k, int start, List<Integer> path, List<List<Integer>> res) {
    if (path.size() == k) {
        res.add(new ArrayList<>(path));
        return;
    }
    // Optimization: if remaining elements are fewer than required, prune
    for (int i = start; i <= n - (k - path.size()) + 1; i++) {
        path.add(i);
        backtrack(n, k, i + 1, path, res);
        path.removeLast();
    }
}

Combination Sum (Reusable Elements)

If you can pick the same number multiple times, pass i instead of i + 1 to the recursive call.

// Inside the loop:
path.add(candidates[i]);
backtrack(candidates, i, target - candidates[i], path, res); // Reuse i
path.removeLast();

3. Permutations

Problem: Given distinct integers, return all orderings.

public void backtrack(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
    if (path.size() == nums.length) {
        res.add(new ArrayList<>(path));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue; // Skip used elements in the current stack frame
        
        used[i] = true;
        path.add(nums[i]);
        backtrack(nums, used, path, res);
        path.removeLast();
        used[i] = false;
    }
}

Pattern Comparison

Essential Pruning Tips

1. Strict Growth: In combinations/subsets, using start prevents [1, 2] being generated after [2, 1].
2. Sort for Performance: For sum-related problems, sorting allows you to break early once the current element exceeds the remaining target.
3. Horizontal vs Vertical: nums[i] == nums[i-1] skips duplicates horizontally (across siblings of the same parent), preventing redundant subtrees.