Permutations and Combinations
What is this?
Enumerating arrangements is the easiest kind of backtracking to write and the easiest to get subtly wrong. The search itself is mechanical: pick something, recurse, put it back. The difficulty is duplicates: when the input contains repeated values, a naive enumeration emits the same arrangement several times, and filtering them afterwards with a set is both slower and a sign that you did not understand where they came from.
The fix is a single line, and knowing exactly why it works is what the interview is testing.
Fun fact: the duplicate-skip condition is
i > start and nums[i] == nums[i-1], and thei > starthalf is what makes it correct. Equal values must be skipped when they are siblings in the recursion tree, because a sibling branch has already generated everything that branch would. They must not be skipped when they are ancestors, because[1, 1]is a perfectly legitimate arrangement of two equal values. One comparison separates the two cases, and getting it wrong drops valid answers rather than duplicates.
🔓 The 6 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
In one line: sort first, then at every level skip a candidate equal to the one just tried at that same level. For validity-constrained enumeration, carry counters instead of generating-then-filtering, so the search only ever walks toward legal answers.
1. Subsets and combinations
def subsets(nums):
nums.sort()
result, path = [], []
def backtrack(start):
result.append(path[:]) # every node is an answer, not just leaves
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i-1]:
continue # sibling duplicate, skip
path.append(nums[i])
backtrack(i + 1)
path.pop() # undo
backtrack(0)
return result
Two things to notice. result.append(path[:]) happens at every node, because every prefix is itself a valid subset, unlike permutations, where only complete leaves count. And path[:] copies; appending path itself stores a reference that later mutations will corrupt, which is one of the most common silent bugs in this family.
2. Permutations with duplicates
Permutations differ because every element is used exactly once, so you need a used array rather than a start index:
for i in range(len(nums)):
if used[i]:
continue
if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
continue # the equal predecessor is unused → sibling duplicate
used[i] = True
path.append(nums[i])
backtrack()
path.pop(); used[i] = False
not used[i-1] is the permutation form of the same idea: if the identical previous value has not been used at this point, choosing this one now duplicates a branch that already ran.
3. Prune, do not filter
Generate Parentheses shows the alternative to duplicate-skipping: constrain the search so invalid states never appear at all:
def gen(path, open_used, close_used):
if len(path) == 2 * n:
result.append(''.join(path)); return
if open_used < n: # can always open while any remain
gen(path + ['('], open_used + 1, close_used)
if close_used < open_used: # only close what has been opened
gen(path + [')'], open_used, close_used + 1)
Every leaf reached is a valid string. Nothing is generated and discarded, so the tree has only O(n * C_n) nodes (C_n is the Catalan number, about 4^n / sqrt(n)) instead of the 2^(2n) strings a generate-then-filter version builds. Note that path + ['('] copies the list on every call, so this form uses O(n^2) space beyond the output; the lesson shows a shared-list version with O(n).
4. A 30-second worked example (why i > start matters)
nums = [1, 1, 2], generating subsets:
The same value is skipped in one place and kept in the other, and i > start is the only thing distinguishing them. Skipping both would lose [1,1]; skipping neither would emit [1] twice.
5. Where you'll actually meet this
- Test-case generation. Enumerating distinct input combinations, where duplicates waste time without adding coverage.
- Configuration search. Trying every valid combination of feature flags or parameters.
- Security tooling. Enumerating candidate arrangements of a key space under constraints.
- Predictive text. Letter Combinations is the original T9 keypad expansion.
- Scheduling and seating. Distinct assignments where interchangeable people or slots must not multiply the result set.
6. Problems in this chapter
Generate Parentheses
All valid combinations of n bracket pairs. Two counters constrain the search so every leaf is valid.
Pattern: counter-pruned generation. Target: O(n * C_n) = O(4^n / sqrt(n)) time; O(n) space beyond the output with a shared list (O(n^2) if you concatenate strings).
Subsets
Every subset of a collection. Record at every node, not only at leaves.
Pattern: start-index backtracking. Target: O(n · 2ⁿ) time, O(n) auxiliary space. The iterative-doubling version needs O(n · 2ⁿ) auxiliary space.
Permutations II
All distinct permutations of a collection containing duplicates. A used array plus the not used[i-1] skip.
Pattern: permutation backtracking with sibling-duplicate skipping. Target: O(n! · n) worst case, fewer with duplicates; O(n) auxiliary space. It sorts the caller's list in place.
Palindrome Permutation II
All palindromes formable by rearranging a string. Check feasibility by character parity first, then permute half the string and mirror it.
Pattern: feasibility check + half-permutation. Target: O(U · n), where U is the number of distinct half-permutations, at most (n/2)!. That is far below n! but is not the square root of it: for n = 10, 120 versus 3,628,800.
Letter Combinations of a Phone Number
Every string from a digit sequence on a phone keypad. Straight product enumeration, one digit per recursion level.
Pattern: cartesian-product backtracking. Target: O(4ⁿ · n) time, O(n) auxiliary space.
Binary Watch
Every time a 10-LED binary watch can show with exactly n LEDs lit. The space is tiny (12 x 60 = 720 times), so the neat version skips backtracking and keeps the pairs whose hour and minute bit counts add up to n.
Pattern: bounded enumeration with a popcount filter. Target: O(720) = O(1) time.
7. Common pitfalls
- Appending
pathinstead ofpath[:]. Storing a reference means later mutations silently corrupt every recorded answer. - Deduplicating with a set at the end. It works, hides the real insight, and costs both time and memory.
- Skipping duplicates without the
i > startguard. Legitimate arrangements of equal values disappear. - Forgetting to sort. The duplicate skip relies on equal values being adjacent.
- Recording only at leaves for subsets. Every node is an answer there; only permutations require completeness.
- Permuting the whole string in Palindrome Permutation II. Permute half and mirror it.
- Skipping the parity check. A string with two odd-count characters has no palindrome at all, and testing that first avoids an entire pointless search.
- Reaching for backtracking on a tiny fixed space. In Binary Watch there are only 720 candidate times, so counting set bits over all of them is simpler than generating LED subsets.
8. Key takeaways
- Sort, then skip sibling duplicates. One line replaces post-filtering entirely.
i > start(ornot used[i-1]) is the whole subtlety: it separates siblings from ancestors.- Copy the path when recording. References are the classic silent corruption.
- Subsets record at every node; permutations only at leaves.
- Prune with counters rather than filtering when validity can be maintained incrementally.
- Check feasibility before searching. A parity test can rule out the whole search space instantly.
- Why interviewers like it: everyone can enumerate. Producing distinct results without a deduplicating set, and explaining why the skip is correct, is the differentiator.
Order: Generate Parentheses → Subsets → Permutations II → Palindrome Permutation II → Letter Combinations of a Phone Number → Binary Watch.
Permutations II
Core idea: When the input can contain repeats, a plain permutation walk produces the same arrangement many times. Sort the array so equal values sit next to each other, then at every level of the recursion refuse to start a branch with a duplicate value unless its identical predecessor has already been placed in the current path. That single guard collapses all the redundant branches and leaves exactly the unique permutations.
Problem, rephrased
A photographer is arranging a group for a photo in which some members are identical twins. Swap two twins and the photo looks exactly the same, so it is not a new arrangement. Each person is tagged with a number, and twins share the same number. You're given the lineup as an integer array nums, which might contain duplicates.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson