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 the i > start half 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 5 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: 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, which is why this is O(Catalan(n)) rather than O(2^(2n)).

4. A 30-second worked example (why i > start matters)

nums = [1, 1, 2], generating subsets:

level 0, start=0:
  i=0 (value 1)  → take it, recurse with start=1
      level 1, start=1:
        i=1 (value 1)  i > start? 1 > 1 is FALSE → do NOT skip
                       → take it → subset [1,1]  ✅ legitimate
  i=1 (value 1)  i > start? 1 > 0 is TRUE and nums[1] == nums[0] → SKIP
                 (the branch starting with the first 1 already covered this)
  i=2 (value 2)  → take it → subset [2]

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(Catalan(n)) results, O(n) recursion depth.

▶ Subsets

Every subset of a collection. Record at every node, not only at leaves.
Pattern: start-index backtracking. Target: O(2ⁿ · n) time.

▶ 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.

▶ 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((n/2)! · n).

▶ 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).

7. Common pitfalls 🚫

• Appending path instead of path[:]. 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 > start guard. 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.

8. Key takeaways

1. Sort, then skip sibling duplicates. One line replaces post-filtering entirely.
2. i > start (or not used[i-1]) is the whole subtlety — it separates siblings from ancestors.
3. Copy the path when recording. References are the classic silent corruption.
4. Subsets record at every node; permutations only at leaves.
5. Prune with counters rather than filtering when validity can be maintained incrementally.
6. Check feasibility before searching. A parity test can rule out the whole search space instantly.
7. 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.