Backtracking (Subsets/Permutations)

The Intuition

Backtracking is depth-first enumeration of a decision tree, with the recursion stack acting as the record of choices made so far. Each frame represents one decision; returning from the frame undoes that decision. The standard skeleton is choose, recurse, unchoose: append to the current path, recurse, pop after the call returns. The pop is the backtrack.

Two foundational shapes cover most problems. Subsets: at each element, decide include or exclude. The decision tree has 2^n leaves. Permutations: at each position, pick any element not already used. The decision tree has n! leaves. Almost every backtracking problem reshapes into one of these two with extra constraints layered on.

Pruning is what makes backtracking tractable in practice. The instant a partial solution violates a constraint, return without exploring further. For N-Queens, if a placement attacks an existing queen, skip the entire subtree of size (n-row)! that would have been explored. For Sudoku, an invalid candidate value cuts off a 9^(remaining-cells) subtree. The earlier the prune, the larger the savings.

The handling of duplicates is its own subpattern. Sort the input first, then at each recursion level, skip nums[i] if nums[i] == nums[i-1] and the previous duplicate was not chosen at this level. For subsets the check is i > start && nums[i] == nums[i-1]. For permutations the check is i > 0 && nums[i] == nums[i-1] && !used[i-1]. The logic differs because subsets advance via a start index while permutations use a used array.

When to use

Generating subsets, permutations, combinations, N-Queens, Sudoku solver, word search, palindrome partitioning, or any constraint-satisfaction problem.

When NOT to use

Problem has optimal substructure (use DP instead)
Input is too large for exponential exploration (need polynomial algorithm)
Only need count not enumeration (use DP or math)

Pattern Recognition

generate all subsets / permutations / combinationsplace N items satisfying constraints (N-Queens, Sudoku, word search)partition the string / array into valid pieces (palindrome partitioning, expression add operators)find all paths in a grid or graphinput size is small (n <= 20 typically) and an exponential exploration is acceptable

Edge Cases

Empty input array
Single element in the input
No valid solution exists for the given constraints
Input contains duplicate elements

Practice Problems

MediumSubsets

MediumPermutations

MediumCombination Sum

HardN-Queens

HardSudoku Solver

Key Points

•Explore all candidates, backtrack when constraint is violated
•For subsets: at each index, choose to include or exclude
•For permutations: swap elements or use a visited array
•Prune early to avoid unnecessary exploration
•Use a path/current list, add to result when complete, then undo

Code Template

def subsets(nums):
    """Generate all subsets."""
    result = []
    def backtrack(start, path):
        result.append(path[:])  # copy current path
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()  # backtrack
    backtrack(0, [])
    return result

def permutations(nums):
    """Generate all permutations."""
    result = []
    def backtrack(path, used):
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack(path, used)
            path.pop()
            used[i] = False
    backtrack([], [False] * len(nums))
    return result

def combination_sum(candidates, target):
    """Find combinations that sum to target (reuse allowed)."""
    result = []
    def backtrack(start, path, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break
            path.append(candidates[i])
            backtrack(i, path, remaining - candidates[i])
            path.pop()
    candidates.sort()
    backtrack(0, [], target)
    return result

def subsets_with_dup(nums):
    """Subsets II: generate all unique subsets when input has duplicates.
    Key idea: sort first, then skip nums[i] if nums[i] == nums[i-1]
    and i-1 was not picked at this recursion level."""
    nums.sort()
    result = []
    def backtrack(start, path):
        result.append(path[:])
        for i in range(start, len(nums)):
            # Skip duplicates at the same level
            if i > start and nums[i] == nums[i - 1]:
                continue
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    backtrack(0, [])
    return result

def permutations_with_dup(nums):
    """Permutations II: generate all unique permutations when
    input has duplicates. Sort first, then skip nums[i] if
    nums[i] == nums[i-1] and nums[i-1] was not used."""
    nums.sort()
    result = []
    used = [False] * len(nums)
    def backtrack(path):
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            # Skip duplicate: same value as previous,
            # and previous was not used at this level
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack(path)
            path.pop()
            used[i] = False
    backtrack([])
    return result

func subsets(nums []int) [][]int {
    // Generate all subsets.
    result := [][]int{}
    var backtrack func(start int, path []int)
    backtrack = func(start int, path []int) {
        tmp := make([]int, len(path))
        copy(tmp, path)
        result = append(result, tmp)
        for i := start; i < len(nums); i++ {
            path = append(path, nums[i])
            backtrack(i+1, path)
            path = path[:len(path)-1] // backtrack
        }
    }
    backtrack(0, []int{})
    return result
}

func permutations(nums []int) [][]int {
    // Generate all permutations.
    result := [][]int{}
    used := make([]bool, len(nums))
    var backtrack func(path []int)
    backtrack = func(path []int) {
        if len(path) == len(nums) {
            tmp := make([]int, len(path))
            copy(tmp, path)
            result = append(result, tmp)
            return
        }
        for i := 0; i < len(nums); i++ {
            if used[i] { continue }
            used[i] = true
            path = append(path, nums[i])
            backtrack(path)
            path = path[:len(path)-1]
            used[i] = false
        }
    }
    backtrack([]int{})
    return result
}

func subsetsWithDup(nums []int) [][]int {
    // Subsets II: unique subsets when input has duplicates.
    // Sort first, skip nums[i] if it equals nums[i-1] at same level.
    sort.Ints(nums)
    result := [][]int{}
    var backtrack func(start int, path []int)
    backtrack = func(start int, path []int) {
        tmp := make([]int, len(path))
        copy(tmp, path)
        result = append(result, tmp)
        for i := start; i < len(nums); i++ {
            // Skip duplicates at the same recursion level
            if i > start && nums[i] == nums[i-1] {
                continue
            }
            path = append(path, nums[i])
            backtrack(i+1, path)
            path = path[:len(path)-1]
        }
    }
    backtrack(0, []int{})
    return result
}

func permutationsWithDup(nums []int) [][]int {
    // Permutations II: unique permutations with duplicates.
    // Sort first, skip if nums[i] == nums[i-1] and i-1 not used.
    sort.Ints(nums)
    result := [][]int{}
    used := make([]bool, len(nums))
    var backtrack func(path []int)
    backtrack = func(path []int) {
        if len(path) == len(nums) {
            tmp := make([]int, len(path))
            copy(tmp, path)
            result = append(result, tmp)
            return
        }
        for i := 0; i < len(nums); i++ {
            if used[i] { continue }
            if i > 0 && nums[i] == nums[i-1] && !used[i-1] {
                continue
            }
            used[i] = true
            path = append(path, nums[i])
            backtrack(path)
            path = path[:len(path)-1]
            used[i] = false
        }
    }
    backtrack([]int{})
    return result
}

public List<List<Integer>> subsets(int[] nums) {
    // Generate all subsets.
    List<List<Integer>> result = new ArrayList<>();
    backtrackSubsets(nums, 0, new ArrayList<>(), result);
    return result;
}

private void backtrackSubsets(int[] nums, int start,
    List<Integer> path, List<List<Integer>> result) {
    result.add(new ArrayList<>(path));
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        backtrackSubsets(nums, i + 1, path, result);
        path.remove(path.size() - 1); // backtrack
    }
}

public List<List<Integer>> permutations(int[] nums) {
    // Generate all permutations.
    List<List<Integer>> result = new ArrayList<>();
    boolean[] used = new boolean[nums.length];
    backtrackPerms(nums, used, new ArrayList<>(), result);
    return result;
}

private void backtrackPerms(int[] nums, boolean[] used,
    List<Integer> path, List<List<Integer>> result) {
    if (path.size() == nums.length) {
        result.add(new ArrayList<>(path));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        used[i] = true;
        path.add(nums[i]);
        backtrackPerms(nums, used, path, result);
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

public List<List<Integer>> subsetsWithDup(int[] nums) {
    // Subsets II: unique subsets when input has duplicates.
    Arrays.sort(nums);
    List<List<Integer>> result = new ArrayList<>();
    backtrackSubsetsII(nums, 0, new ArrayList<>(), result);
    return result;
}

private void backtrackSubsetsII(int[] nums, int start,
    List<Integer> path, List<List<Integer>> result) {
    result.add(new ArrayList<>(path));
    for (int i = start; i < nums.length; i++) {
        // Skip duplicates at the same recursion level
        if (i > start && nums[i] == nums[i - 1]) continue;
        path.add(nums[i]);
        backtrackSubsetsII(nums, i + 1, path, result);
        path.remove(path.size() - 1);
    }
}

public List<List<Integer>> permutationsWithDup(int[] nums) {
    // Permutations II: unique permutations with duplicates.
    Arrays.sort(nums);
    List<List<Integer>> result = new ArrayList<>();
    boolean[] used = new boolean[nums.length];
    backtrackPermsII(nums, used, new ArrayList<>(), result);
    return result;
}

private void backtrackPermsII(int[] nums, boolean[] used,
    List<Integer> path, List<List<Integer>> result) {
    if (path.size() == nums.length) {
        result.add(new ArrayList<>(path));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        // Skip duplicate: same as previous, previous not used
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])
            continue;
        used[i] = true;
        path.add(nums[i]);
        backtrackPermsII(nums, used, path, result);
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

Common Mistakes

Forgetting to undo the choice (backtrack) after recursion
Not skipping duplicates when input has repeated elements
Modifying the result list reference instead of copying it

Related Patterns

The Intuition

def subsets(nums): """Generate all subsets.""" result = [] def backtrack(start, path): result.append(path[:]) # copy current path for i in range(start, len(nums)): path.append(nums[i]) backtrack(i + 1, path) path.pop() # backtrack backtrack(0, []) return result def permutations(nums): """Generate all permutations.""" result = [] def backtrack(path, used): if len(path) == len(nums): result.append(path[:]) return for i in range(len(nums)): if used[i]: continue used[i] = True path.append(nums[i]) backtrack(path, used) path.pop() used[i] = False backtrack([], [False] * len(nums)) return result def combination_sum(candidates, target): """Find combinations that sum to target (reuse allowed).""" result = [] def backtrack(start, path, remaining): if remaining == 0: result.append(path[:]) return for i in range(start, len(candidates)): if candidates[i] > remaining: break path.append(candidates[i]) backtrack(i, path, remaining - candidates[i]) path.pop() candidates.sort() backtrack(0, [], target) return result def subsets_with_dup(nums): """Subsets II: generate all unique subsets when input has duplicates. Key idea: sort first, then skip nums[i] if nums[i] == nums[i-1] and i-1 was not picked at this recursion level.""" nums.sort() result = [] def backtrack(start, path): result.append(path[:]) for i in range(start, len(nums)): # Skip duplicates at the same level if i > start and nums[i] == nums[i - 1]: continue path.append(nums[i]) backtrack(i + 1, path) path.pop() backtrack(0, []) return result def permutations_with_dup(nums): """Permutations II: generate all unique permutations when input has duplicates. Sort first, then skip nums[i] if nums[i] == nums[i-1] and nums[i-1] was not used.""" nums.sort() result = [] used = [False] * len(nums) def backtrack(path): if len(path) == len(nums): result.append(path[:]) return for i in range(len(nums)): if used[i]: continue # Skip duplicate: same value as previous, # and previous was not used at this level if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]: continue used[i] = True path.append(nums[i]) backtrack(path) path.pop() used[i] = False backtrack([]) return result

func subsets(nums []int) [][]int { // Generate all subsets. result := [][]int{} var backtrack func(start int, path []int) backtrack = func(start int, path []int) { tmp := make([]int, len(path)) copy(tmp, path) result = append(result, tmp) for i := start; i < len(nums); i++ { path = append(path, nums[i]) backtrack(i+1, path) path = path[:len(path)-1] // backtrack } } backtrack(0, []int{}) return result } func permutations(nums []int) [][]int { // Generate all permutations. result := [][]int{} used := make([]bool, len(nums)) var backtrack func(path []int) backtrack = func(path []int) { if len(path) == len(nums) { tmp := make([]int, len(path)) copy(tmp, path) result = append(result, tmp) return } for i := 0; i < len(nums); i++ { if used[i] { continue } used[i] = true path = append(path, nums[i]) backtrack(path) path = path[:len(path)-1] used[i] = false } } backtrack([]int{}) return result } func subsetsWithDup(nums []int) [][]int { // Subsets II: unique subsets when input has duplicates. // Sort first, skip nums[i] if it equals nums[i-1] at same level. sort.Ints(nums) result := [][]int{} var backtrack func(start int, path []int) backtrack = func(start int, path []int) { tmp := make([]int, len(path)) copy(tmp, path) result = append(result, tmp) for i := start; i < len(nums); i++ { // Skip duplicates at the same recursion level if i > start && nums[i] == nums[i-1] { continue } path = append(path, nums[i]) backtrack(i+1, path) path = path[:len(path)-1] } } backtrack(0, []int{}) return result } func permutationsWithDup(nums []int) [][]int { // Permutations II: unique permutations with duplicates. // Sort first, skip if nums[i] == nums[i-1] and i-1 not used. sort.Ints(nums) result := [][]int{} used := make([]bool, len(nums)) var backtrack func(path []int) backtrack = func(path []int) { if len(path) == len(nums) { tmp := make([]int, len(path)) copy(tmp, path) result = append(result, tmp) return } for i := 0; i < len(nums); i++ { if used[i] { continue } if i > 0 && nums[i] == nums[i-1] && !used[i-1] { continue } used[i] = true path = append(path, nums[i]) backtrack(path) path = path[:len(path)-1] used[i] = false } } backtrack([]int{}) return result }

public List<List<Integer>> subsets(int[] nums) { // Generate all subsets. List<List<Integer>> result = new ArrayList<>(); backtrackSubsets(nums, 0, new ArrayList<>(), result); return result; } private void backtrackSubsets(int[] nums, int start, List<Integer> path, List<List<Integer>> result) { result.add(new ArrayList<>(path)); for (int i = start; i < nums.length; i++) { path.add(nums[i]); backtrackSubsets(nums, i + 1, path, result); path.remove(path.size() - 1); // backtrack } } public List<List<Integer>> permutations(int[] nums) { // Generate all permutations. List<List<Integer>> result = new ArrayList<>(); boolean[] used = new boolean[nums.length]; backtrackPerms(nums, used, new ArrayList<>(), result); return result; } private void backtrackPerms(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> result) { if (path.size() == nums.length) { result.add(new ArrayList<>(path)); return; } for (int i = 0; i < nums.length; i++) { if (used[i]) continue; used[i] = true; path.add(nums[i]); backtrackPerms(nums, used, path, result); path.remove(path.size() - 1); used[i] = false; } } public List<List<Integer>> subsetsWithDup(int[] nums) { // Subsets II: unique subsets when input has duplicates. Arrays.sort(nums); List<List<Integer>> result = new ArrayList<>(); backtrackSubsetsII(nums, 0, new ArrayList<>(), result); return result; } private void backtrackSubsetsII(int[] nums, int start, List<Integer> path, List<List<Integer>> result) { result.add(new ArrayList<>(path)); for (int i = start; i < nums.length; i++) { // Skip duplicates at the same recursion level if (i > start && nums[i] == nums[i - 1]) continue; path.add(nums[i]); backtrackSubsetsII(nums, i + 1, path, result); path.remove(path.size() - 1); } } public List<List<Integer>> permutationsWithDup(int[] nums) { // Permutations II: unique permutations with duplicates. Arrays.sort(nums); List<List<Integer>> result = new ArrayList<>(); boolean[] used = new boolean[nums.length]; backtrackPermsII(nums, used, new ArrayList<>(), result); return result; } private void backtrackPermsII(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> result) { if (path.size() == nums.length) { result.add(new ArrayList<>(path)); return; } for (int i = 0; i < nums.length; i++) { if (used[i]) continue; // Skip duplicate: same as previous, previous not used if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; used[i] = true; path.add(nums[i]); backtrackPermsII(nums, used, path, result); path.remove(path.size() - 1); used[i] = false; } }