Backtracking (Subsets/Permutations)
The Intuition
Imagine you're solving a combination lock with 4 dials, and you have no idea what the code is. You try 0-0-0-0. Doesn't work. You try 0-0-0-1. Doesn't work. You could keep incrementing the last dial all the way through 9, then roll the third dial forward by 1 and start the last dial over. You're systematically trying every combination by making one choice at a time, and when you exhaust all options at one position, you step back to the previous position and try its next option.
That stepping-back is the "backtracking." You don't start over from scratch when you hit a dead end. You rewind exactly one decision, try the next possibility, and continue forward. Your function call stack keeps a perfect record of every decision you've made so far, and returning from a function call is the act of undoing your last choice. Push an element onto your path, recurse, then pop it off when you come back. The pop is the backtrack.
What makes backtracking powerful is pruning. Suppose you know the first digit can't be 0 because of some constraint. Now you skip all 1,000 combinations starting with 0 in one shot. Every constraint you can check early eliminates an entire branch of the search tree. For N-Queens, the moment you place a queen that attacks another, you don't bother filling in the remaining rows. You backtrack immediately. For Sudoku, if a number violates a row, column, or box constraint, you move on to the next candidate number without exploring further.
Subsets and permutations are the two foundational shapes. For subsets, each element presents a binary choice: include it or skip it. That gives you 2^n possibilities. For permutations, each position can be filled by any unused element, giving you n! possibilities. Once you see that every backtracking problem is just one of these two shapes (or a constrained version of them), the template becomes second nature.
Generating subsets, permutations, combinations, N-Queens, Sudoku solver, word search, palindrome partitioning, or any constraint-satisfaction problem.
- 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)
Variations:
- Subsets: Include/exclude each element; O(2^n) subsets.
- Permutations: Try each unused element at each position; O(n!) permutations.
- Combinations: Choose k elements from n with order irrelevant.
- Constraint backtracking: Prune branches that violate constraints early (N-Queens, Sudoku).
Handling Duplicates (Subsets II / Permutations II)
When the input contains duplicate elements, the basic templates will produce duplicate results. For example, [1, 1, 2] has only 3 unique subsets of size 2: {1,1}, {1,2}, {1,2} would appear twice without dedup.
The fix is straightforward: sort the input first, then at each recursion level, skip nums[i] if it equals nums[i-1] and i-1 was not chosen at this level. Sorting groups identical values together, and the skip condition ensures you only pick the first occurrence of each value at any given decision point. This avoids generating the same subset or permutation twice without needing a hash set.
For subsets, the check is i > start && nums[i] == nums[i-1]. For permutations, it is i > 0 && nums[i] == nums[i-1] && !used[i-1]. The logic is slightly different because subsets use a start index to avoid revisiting earlier elements, while permutations use a used array.
- Empty input array
- Single element in the input
- No valid solution exists for the given constraints
- Input contains duplicate elements
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
1 def subsets(nums):
2 """Generate all subsets."""
3 result = []
4 def backtrack(start, path):
5 result.append(path[:]) # copy current path
6 for i in range(start, len(nums)):
7 path.append(nums[i])
8 backtrack(i + 1, path)
9 path.pop() # backtrack
10 backtrack(0, [])
11 return result
12
13 def permutations(nums):
14 """Generate all permutations."""
15 result = []
16 def backtrack(path, used):
17 if len(path) == len(nums):
18 result.append(path[:])
19 return
20 for i in range(len(nums)):
21 if used[i]:
22 continue
23 used[i] = True
24 path.append(nums[i])
25 backtrack(path, used)
26 path.pop()
27 used[i] = False
28 backtrack([], [False] * len(nums))
29 return result
30
31 def combination_sum(candidates, target):
32 """Find combinations that sum to target (reuse allowed)."""
33 result = []
34 def backtrack(start, path, remaining):
35 if remaining == 0:
36 result.append(path[:])
37 return
38 for i in range(start, len(candidates)):
39 if candidates[i] > remaining:
40 break
41 path.append(candidates[i])
42 backtrack(i, path, remaining - candidates[i])
43 path.pop()
44 candidates.sort()
45 backtrack(0, [], target)
46 return result
47
48 def subsets_with_dup(nums):
49 """Subsets II: generate all unique subsets when input has duplicates.
50 Key idea: sort first, then skip nums[i] if nums[i] == nums[i-1]
51 and i-1 was not picked at this recursion level."""
52 nums.sort()
53 result = []
54 def backtrack(start, path):
55 result.append(path[:])
56 for i in range(start, len(nums)):
57 # Skip duplicates at the same level
58 if i > start and nums[i] == nums[i - 1]:
59 continue
60 path.append(nums[i])
61 backtrack(i + 1, path)
62 path.pop()
63 backtrack(0, [])
64 return result
65
66 def permutations_with_dup(nums):
67 """Permutations II: generate all unique permutations when
68 input has duplicates. Sort first, then skip nums[i] if
69 nums[i] == nums[i-1] and nums[i-1] was not used."""
70 nums.sort()
71 result = []
72 used = [False] * len(nums)
73 def backtrack(path):
74 if len(path) == len(nums):
75 result.append(path[:])
76 return
77 for i in range(len(nums)):
78 if used[i]:
79 continue
80 # Skip duplicate: same value as previous,
81 # and previous was not used at this level
82 if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
83 continue
84 used[i] = True
85 path.append(nums[i])
86 backtrack(path)
87 path.pop()
88 used[i] = False
89 backtrack([])
90 return resultCommon 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