Permutations & Combinations

Build each answer exactly once

A coach has 20 players and wants a list of every possible 10-player squad. Here is a plan that sounds reasonable: generate every ordered line-up of 10 different players, sort each one, and let a set throw away the repeats.

That plan builds P(20, 10) = 670,442,572,800 line-ups. There are only C(20, 10) = 184,756 different squads, so every squad gets built 10! = 3,628,800 times before the set discards the copies. No hash set is fast enough to rescue that.

The fix is not a faster way to remove duplicates. It is a way of building answers in which every answer has exactly one construction, so there is nothing to remove.

Every problem in this lesson runs the same machine. Walk a decision tree depth-first, add one choice per level, record the path when it is complete, then undo the choice and try the next one. Only two knobs change from family to family:

1. Which choices are allowed at the next level.
2. When a path counts as an answer.

Set both knobs correctly and the tree contains each answer once. This lesson covers six settings.

This lesson builds on Advanced Recursion & Backtracking: the call stack, the choose/explore/unchoose template, why a finished path is copied before it is stored, and pruning. Here that template is applied to the families that generate arrangements and selections. The count vectors from Foundation: Arrays & Strings come back in Move 4. All code is Python 3, and itertools appears only as a trusted reference for testing.

The machine, in outline

result = []
path = []                                  # the one live list of choices, root to here

backtrack(state):
    if path is a finished answer:          # knob 2
        result.append(copy of path)        # path keeps changing, so store a snapshot
        return                             # subsets skip this return: record, then keep going
    for choice in allowed(state):          # knob 1
        path.append(choice)                # choose
        backtrack(next state)              # explore
        path.pop()                         # unchoose

Each move below fills in allowed, next state and "finished" differently. Keep the outline in mind and the six moves are one idea.

Before any code: count the answers

A generator has to write out every answer, so (number of answers) × (length of each answer) is a floor on its running time. Count first. The count tells you whether the problem is feasible, and it gives your tests a number to check.

Every row except the multisets row comes from filling slots: n choices for the first seat, n − 1 for the second, and so on. The multisets row needs a different argument ("stars and bars"). Dividing the 4³ ordered scoop sequences by 3! fails (it gives 10.67), because a sequence with a repeated flavour has fewer than 3! orderings. The answer is C(6, 3) = 20. A combination is a k-permutation with the order forgotten. Each group of k appears in k! orders, so C(n, k) = P(n, k) / k!. The same "divide out what you can't tell apart" argument gives the repeated-values row: swapping two equal 1s gives back the same list, so the c₁! orderings of the 1s count once. Python has these built in: math.factorial(n), math.perm(n, k) and math.comb(n, k).

Predict first: one problem says n ≤ 12 and asks you to return every arrangement. Another says n ≤ 20 and asks for every subset. Which one is hopeless?

A working rule: listing every permutation is practical up to about n = 10, and listing every subset up to about n = 20. LeetCode's limits sit safely inside these: Permutations caps n at 6, Permutations II at 8, and Subsets at 10. Read the constraint as a hint about the family.

⚠️ Count, don't generate. When a problem asks only how many, don't list anything. The number of 5-card hands from a 52-card deck is math.comb(52, 5) = 2,598,960, computed instantly. When the count comes with conditions attached, dynamic programming usually counts without listing. See Dynamic Programming Mastery.

🧠 Why not memoize the generator? The subproblem "all arrangements of the remaining items" does repeat. For n = 4 the recursion makes 65 calls but meets only 16 different remaining sets, and it reaches the empty set 24 times. Caching still doesn't help, because every one of the n! answers must be written out in full. A cache can only skip work the output doesn't force on you. When the question is a count, that repetition is exactly what DP exploits.

Move 1: Pick any unused item (permutations)

Smell: the expected output treats [1, 2] and [2, 1] as different answers, and every item appears exactly once in each answer.

LeetCode 46: Permutations asks for every arrangement of up to 6 distinct integers. Level d of the tree decides what goes in position d. The root has n children, each of those has n − 1, and so on down to n! leaves:

                     []
          /           |           \
        [1]          [2]          [3]
       /   \        /   \        /   \
    [1,2] [1,3]  [2,1] [2,3]  [3,1] [3,2]
      |     |      |     |      |     |
 [1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]

Predict first: the code below tries unused indices smallest first. For [1, 2, 3], which arrangement does it record fourth? And how many times is backtrack called in total?

The slow version tries every tuple of n picks and keeps those with no repeated item, for example itertools.product(nums, repeat=n) plus a filter. For n = 8 that is 8⁸ = 16,777,216 tuples, of which 40,320 survive, so 99.76% are thrown away. The waste comes from picking an item that is already in the path and only noticing at the very end. The fix is to check before you go deeper.

def permute(nums):
    n = len(nums)
    result, path = [], []
    used = [False] * n

    def backtrack():
        if len(path) == n:              # every position is filled
            result.append(path[:])      # store a snapshot, not the live list
            return
        for i in range(n):
            if used[i]:
                continue
            used[i] = True              # choose
            path.append(nums[i])
            backtrack()                 # explore
            path.pop()                  # unchoose, in reverse order
            used[i] = False

    backtrack()
    return result

The first twelve events for permute([1, 2, 3]), printed by an instrumented copy:

Then 2 goes first and the pattern repeats. The full output is [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]].

Why it works

Invariant: at every call, used[i] is True exactly for the indices already in path. Each choose sets one flag and each unchoose clears it in reverse order, so the invariant holds before and after every call. The loop therefore offers exactly the unused items.

Every arrangement p comes out once: at depth d the loop reaches the index of p[d] exactly once, and that index is still unused because p has no repeats. Nothing else comes out, because a path can reach length n only with n different indices.

Cost. Depth d of the tree has n!/(n − d)! nodes, which adds up to n! · (1 + 1/1! + 1/2! + …), less than e · n! ≈ 2.72 · n!. For n = 3 that is 16 nodes. Each node runs an O(n) loop and each leaf copies n items, so the time is O(n · n!). Saying O(n!) misses that each of the n! answers is n numbers long. Extra space besides the output is O(n): path, used, and at most n + 1 stack frames. The output itself holds n · n! numbers. Recursion depth never comes near Python's default limit of 1,000, because the output explodes long before the stack does.

⚠️ A hidden quadratic. Many tutorials pass shrinking copies instead of a used array: backtrack(path, remaining[:i] + remaining[i+1:]). That version is correct, but every call builds a new list, and the lists along the current path (sizes n − 1, n − 2, …, 1) are all alive at once. That costs O(n²) extra space instead of O(n), plus O(n) extra time per call.

Variation: swap in place

def permute_swap(nums):
    nums = nums[:]                      # work on a copy; the caller's list stays as it was
    n = len(nums)
    result = []

    def backtrack(first):
        if first == n:
            result.append(nums[:])
            return
        for i in range(first, n):
            nums[first], nums[i] = nums[i], nums[first]   # move nums[i] into position first
            backtrack(first + 1)
            nums[first], nums[i] = nums[i], nums[first]   # swap back

    backtrack(0)
    return result

Invariant: before backtrack(first), nums[:first] is the fixed prefix of the current arrangement and nums[first:] holds exactly the items not yet placed. The first swap chooses, and the second swap undoes the choice.

permute_swap([1, 2, 3]) returns [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]. The last two are not in sorted order: swapping 1 and 3 leaves the suffix as [2, 1]. LeetCode accepts any order, but a test that compares lists position by position would not.

You may have heard that "permutations use a used array and combinations use a start index". That is half true. The swap version has an index too. first means "the next position to fill", and the swaps keep every unused item to its right. What a permutation generator must never do is refuse the items to the left of a pointer forever. That refusal is what makes combinations.

Edge case: permute([]) returns [[]], one arrangement of nothing, which matches 0! = 1. LeetCode's n ≥ 1 means it won't test this, but your own tests should agree on it.

Your turn: write arrangements(nums, k), which returns every ordered pick of k distinct positions. Predict the count for [1, 2, 3, 4] with k = 2, name the one line that changes, and say what k > n returns.

def arrangements(nums, k):
    n = len(nums)
    result, path = [], []
    used = [False] * n

    def backtrack():
        if len(path) == k:              # the only change: stop after k picks
            result.append(path[:])
            return
        for i in range(n):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack()
            path.pop()
            used[i] = False

    backtrack()
    return result

Move 2: Only look forward (combinations)

Smell: the problem says "choose k", "team" or "group", and [1, 2] and [2, 1] count as the same answer. If the example output shows only one of them, you need combinations.

LeetCode 77: Combinations asks for every group of k numbers from 1 to n (n ≤ 20).

Predict first: run arrangements([1, 2, 3, 4], 2) from Move 1. How many lists come out? How many different groups of two are there, and how many times does each group appear?

A group of k items can be written in k! orders, but only one of them lists the indices in increasing order. So build only that one: after picking index i, the next pick must come from index i + 1 or later.

def combine(items, k):
    result, path = [], []

    def backtrack(start):
        if len(path) == k:
            result.append(path[:])
            return
        for i in range(start, len(items)):
            path.append(items[i])
            backtrack(i + 1)            # the next pick must come from a later index
            path.pop()

    backtrack(0)
    return result

For LeetCode 77, call combine(list(range(1, n + 1)), k). Keeping one convention, where i is always an index and items[i] is always a value, avoids the classic off-by-one of mixing 1-based values with 0-based indices.

Every call of combine([1, 2, 3, 4], 2), in order:

The output is [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]. [2, 1] can never be built, because once the path holds 2, index 0 is behind start.

Why it works. Invariant: the indices in path strictly increase, and every index still to be picked is at least start. Each group has exactly one increasing listing, and at every depth the loop reaches that listing's next index exactly once. So each group appears once and no reordering is ever built.

One argument, four families

The argument you pass to the recursive call decides what you generate. Here is what each choice prints on [1, 2, 3] with k = 2:

The third row is a classic bug. Forgetting to advance start doesn't only allow repeats. It also brings back the reorderings, such as [2, 1]. The second row is exactly what Move 5 needs.

Pruning: leave room for the remaining picks

If you still need need more items (this pick included), the current pick can't come later than index len(items) − need. Otherwise too few items are left to finish. Put that bound in the loop:

def combine_pruned(items, k):
    result, path = [], []

    def backtrack(start):
        if len(path) == k:
            result.append(path[:])
            return
        need = k - len(path)
        for i in range(start, len(items) - need + 1):   # leave room for the other picks
            path.append(items[i])
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return result

Measured call counts on items 1..20:

With small k, pruning barely matters, because almost every branch can still finish. With k close to n it matters enormously: the unpruned search walks nearly the whole 2²⁰ tree to find 190 answers. It never beats the output, though.

Cost. With pruning, every node lies on the way to at least one answer. Each answer's root-to-leaf path has k + 1 nodes, so the tree has at most (k + 1) · C(n, k) nodes, and time is O(k · C(n, k)) and extra space is O(k). C(n, k) peaks at k = n/2, where C(20, 10) = 184,756.

Edge cases: k = 0 gives [[]] (one empty group), and k > n gives [] (the pruned loop is empty immediately). LeetCode 77 promises 1 ≤ k ≤ n.

Your turn: with the pruned loop, which values can be the first pick in combine_pruned([1, 2, 3, 4, 5], 3)? The unpruned version makes 26 calls. Which nodes does pruning remove, and how many calls remain?

Move 3: Record every node (subsets)

Smell: "all subsets", "power set", any size including empty.

LeetCode 78: Subsets asks for every subset of up to 10 distinct integers.

Predict first: the combination code records a path only when it holds k items. Suppose it recorded every path, as soon as each call starts. What would it print for [1, 2, 3], in order?

def subsets(nums):
    result, path = [], []

    def backtrack(start):
        result.append(path[:])          # every node is an answer
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return result

There is no base case. When start == len(nums) the loop is empty and the call simply returns.

The other tree: take it or leave it

You can also make one decision per item: take it or leave it. Answers sit only at the leaves.

def subsets_binary(nums):
    result, path = [], []

    def decide(i):
        if i == len(nums):              # a decision has been made for every item
            result.append(path[:])
            return
        path.append(nums[i])            # take nums[i]
        decide(i + 1)
        path.pop()                      # leave nums[i]
        decide(i + 1)

    decide(0)
    return result

take 1?            yes                          no
take 2?       yes        no               yes        no
take 3?     yes   no   yes   no         yes   no   yes   no
         [1,2,3] [1,2] [1,3]  [1]      [2,3]  [2]   [3]   []

It returns the same 8 subsets in the order shown along the bottom row. The binary tree has 2ⁿ⁺¹ − 1 = 15 nodes for n = 3. The start-index tree has 8, one per answer.

Without recursion

def subsets_iterative(nums):
    result = [[]]
    for x in nums:
        result += [s + [x] for s in result]   # every subset so far, now also with x
    return result

def subsets_bitmask(nums):
    n = len(nums)
    return [[nums[i] for i in range(n) if mask >> i & 1] for mask in range(1 << n)]

The doubling version builds [], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]. The bitmask version maps bit i of mask to nums[i], and the two produce the same order: after the loop, result[m] is the subset whose mask is m.

Cost. Every version produces 2ⁿ answers whose sizes add up to n · 2ⁿ⁻¹, so every version takes O(n · 2ⁿ) time. The recursive versions need O(n) extra space for the path and stack. Don't expect the bitmask version to be the fast one in Python. In a CPython run at n = 16 and n = 18 it was 3 to 4 times slower than subsets, because it tests all n bits of every mask, and the doubling version was the fastest of the four.

Subsets are just all the combination sizes together: 2ⁿ = C(n, 0) + C(n, 1) + … + C(n, n). For n = 3 that is 1 + 3 + 3 + 1 = 8.

Your turn: without running anything, what is subsets_iterative(['a', 'b', 'c'])[6], and which mask gives the same subset? Which subset does mask 5 (binary 101) mean?

Move 4: Sort, then skip an equal twin (duplicates)

Smell: the input may repeat values, but the output must not repeat answers. See LeetCode 90: Subsets II and LeetCode 47: Permutations II.

Predict first: subsets([1, 2, 2]) from Move 3 returns 8 lists. How many different subsets are there, and which lists are repeats?

Duplicates come from one place: two equal values tried at the same level. Choosing the second 2 there starts the path with the same value as choosing the first 2, and what it can add afterwards (nums[3:], nothing) is a suffix of what the first 2 can add (nums[2:], one more 2). So the second 2's branch can only rebuild answers the first 2's branch already built: [2] here, while [2, 2] comes from the first branch alone. So the rule is: at each level, try each distinct value once. Sorting puts equal values next to each other, so "same value as the previous iteration" becomes a single comparison.

def subsets_with_dup(nums):
    nums = sorted(nums)                 # equal values side by side; the caller's list is untouched
    result, path = [], []

    def backtrack(start):
        result.append(path[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue                # this value was already tried at this level
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return result

Every loop step for [1, 2, 2]:

The recorded answers are [], [1], [1, 2], [1, 2, 2], [2], [2, 2].

Why i > start and not i > 0. The first iteration of a level is never a repeat at that level. In the third row, nums[2] == nums[1], but that earlier 2 was never an alternative tried at this level. It is already in the path. With i > 0 that row would be skipped, [1, 2, 2] and [2, 2] would vanish, and the output would be [[], [1], [1, 2], [2]].

Permutations with repeated values

The used-array loop in Move 1 starts at index 0 on every level, so i > start has nothing to compare against. The rule becomes: equal values must be placed in left-to-right order. Call the two 1s 1a and 1b. 1b may be placed only when 1a is already in the path.

def permute_unique(nums):
    nums = sorted(nums)
    n = len(nums)
    result, path = [], []
    used = [False] * n

    def backtrack():
        if len(path) == n:
            result.append(path[:])
            return
        for i in range(n):
            if used[i]:
                continue
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue                # the left twin must be placed first
            used[i] = True
            path.append(nums[i])
            backtrack()
            path.pop()
            used[i] = False

    backtrack()
    return result

Why it works. Any arrangement of the values can be labelled in exactly one way that keeps each value's copies in left-to-right order (1a before 1b). The rule allows only that labelling, so each distinct arrangement appears exactly once, and there are n! / (c₁! · c₂! · …) of them.

Every loop decision for [1, 1, 2]:

That is 9 calls for the 3 answers.

⚠️ Borrowing the subsets rule breaks permutations. if i > 0 and nums[i] == nums[i - 1]: continue, without the used check, blocks 1b forever, even after 1a has been placed. No path ever reaches length 3, so [1, 1, 2] returns [].

⚠️ Forgetting to sort. The rule compares neighbours only. [1, 2, 1] then returns all six lists, repeats included.

⚠️ Sorting the caller's list. nums.sort() inside the function reorders the list the caller passed in. nums = sorted(nums) sorts a copy.

🧠 Plot twist. Flip the rule to and used[i - 1], which skips when the twin is in the path, and the output is still correct. The copies are now forced right to left. But this version rejects bad branches much later. On [1, 1, 1, 1, 2, 2, 2] it makes 1,192 calls instead of 125. Keep not used[i - 1].

A counter instead of a sort

from collections import Counter

def permute_unique_counter(nums):
    counts = Counter(nums)
    n = len(nums)
    result, path = [], []

    def backtrack():
        if len(path) == n:
            result.append(path[:])
            return
        for value in counts:            # each distinct value at most once per level
            if counts[value] == 0:
                continue
            counts[value] -= 1
            path.append(value)
            backtrack()
            path.pop()
            counts[value] += 1

    backtrack()
    return result

Each level loops over distinct values, so it can't pick "a 1" twice at the same level. There is no sort and no skip rule. This is the count vector from the Foundation lesson again: when identities don't matter, remember counts. Only the values change, never the keys, so iterating over counts while updating it is safe.

Cost. Let U = n! / (c₁! · c₂! · …) be the number of answers. Every node is a distinct prefix that can still be completed, so there are at most (n + 1) · U nodes, each with an O(n) loop. That gives O(n² · U) time as a safe bound, of which n · U is writing the output. Extra space is O(n). The dedupe-afterwards alternative, set(itertools.permutations(nums)), builds all n! tuples. On [1, 1, 2, 2, 3, 3, 4, 4, 5, 5] that is 3,628,800 tuples built to keep 113,400, so 32 are built for every one kept.

Your turn: predict how many lists permute_unique([2, 2, 1, 1]) returns, and the first three in order.

Move 5: Carry the remainder (target sums)

Smell: the picks must add up to a target, order doesn't matter, and items may or may not be reused.

LeetCode 39: Combination Sum gives distinct candidates between 2 and 40, lets you use each one any number of times, and caps the target at 40. The statement promises fewer than 150 answers.

Predict first: with candidates [2, 3, 6, 7] and target 7, what is the answer? And what would the unchanged combination template (next call gets i + 1) return?

def combination_sum(candidates, target):
    candidates = sorted(candidates)
    result, path = [], []

    def backtrack(start, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break                   # sorted, so every later candidate is too big as well
            path.append(candidates[i])
            backtrack(i, remaining - candidates[i])    # i, not i + 1: the same item may repeat
            path.pop()

    backtrack(0, target)
    return result

Every loop step for candidates [2, 3] and target 5:

The output is [[2, 3]]. [3, 2] can't appear, because after taking 3 the loop starts at 3's index.

Why break is safe. The candidates are sorted and all positive, so once candidates[i] > remaining, every later candidate is too big as well. continue would give the same output more slowly. On [2, 3, 6, 7] with target 7, the break version makes 10 calls, while a version that recurses first and returns on remaining < 0 makes 28. Without sorting, break is a bug. Candidates [5, 2] with target 4 stop at the 5 and return [] instead of [[2, 2]].

Why it stops at all. Every call subtracts a positive amount, so the path is at most target / min(candidates) long. LeetCode guarantees candidates ≥ 2. If a candidate could be 0, passing i would call backtrack(i, remaining) with the same arguments forever, and Python would raise RecursionError after about 1,000 frames. Every recursive call must shrink the problem.

Cost. Let T be the target and m the smallest candidate. Extra space is O(T/m) for the path and stack, which is 20 levels at most under LeetCode's limits. A loose time bound: at most n branches per node and depth at most T/m, so O(n^(T/m)) nodes, plus copying each answer. Sorting and break keep the real tree far smaller, as the 10 calls above show.

Each item at most once: Combination Sum II

In LeetCode 40: Combination Sum II the candidates may repeat, each may be used at most once, and the output must not repeat a combination. That is Subsets II plus a remainder: sort, skip twins with i > start, pass i + 1, and break when a candidate is too big.

def combination_sum2(candidates, target):
    candidates = sorted(candidates)
    result, path = [], []

    def backtrack(start, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        for i in range(start, len(candidates)):
            if i > start and candidates[i] == candidates[i - 1]:
                continue                # this value was already tried at this level
            if candidates[i] > remaining:
                break
            path.append(candidates[i])
            backtrack(i + 1, remaining - candidates[i])  # each item at most once
            path.pop()

    backtrack(0, target)
    return result

For candidates [10, 1, 2, 7, 6, 1, 5] and target 8 it returns [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]. [1, 1, 6] uses both 1s, taken at different levels, and [1, 7] appears once even though there are two 1s to start it with.

Your turn: LeetCode 216: Combination Sum III asks for every set of k distinct numbers from 1 to 9 that adds up to n. Which row of the four-families table is it? Write it, then predict the output for k = 3, n = 9 and for k = 4, n = 1.

def combination_sum3(k, n):
    result, path = [], []

    def backtrack(start, remaining):
        if len(path) == k:
            if remaining == 0:
                result.append(path[:])
            return
        for x in range(start, 10):
            if x > remaining:
                break                   # x only grows from here
            path.append(x)
            backtrack(x + 1, remaining - x)
            path.pop()

    backtrack(1, n)
    return result

Move 6: Take the cross product (one from each group)

Smell: there are several groups, you pick exactly one option from each, and the order of the groups is fixed by the input. Nothing is rearranged and nothing is left out.

LeetCode 17: Letter Combinations of a Phone Number gives 1 to 4 digits from 2 to 9 and asks for every string the keypad letters could spell.

Predict first: how many strings do the digits "79" give? And "234"? Which string comes fifth for "29"?

KEYPAD = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
          "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}

def letter_combinations(digits):
    result, path = [], []

    def backtrack(pos):
        if pos == len(digits):
            result.append("".join(path))
            return
        for letter in KEYPAD[digits[pos]]:   # depth = position, branching = that digit's letters
            path.append(letter)
            backtrack(pos + 1)
            path.pop()

    backtrack(0)
    return result

letter_combinations("23") returns ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']. Joining builds a new string, so no copy of path is needed here.

Cost. With n digits there are at most 4ⁿ strings, each joined in O(n), so time is O(n · 4ⁿ) and extra space is O(n). Under LeetCode's limit of 4 digits that is at most 256 strings.

Edge case: the empty string. The constraints rule it out, but your contract might not. This code returns [''] for "": one way to pick nothing from no groups, just as 0! = 1. Earlier versions of this problem allowed "" and expected [], which takes one line: if not digits: return []. Decide it; don't discover it.

The title misleads. The problem is called "letter combinations", but the answer is neither combinations nor permutations: the groups are fixed and in order. It is itertools.product, which makes a handy test reference:

from itertools import product

def letter_combinations_reference(digits):
    return ["".join(p) for p in product(*(KEYPAD[d] for d in digits))]

Your turn: generalize the idea to cross(groups), which takes a list of option lists and picks one option from each. Predict the output for [[1, 2], [3], [4, 5, 6]] and for [[1, 2], [], [3]].

def cross(groups):
    result, path = [], []

    def backtrack(pos):
        if pos == len(groups):
            result.append(path[:])
            return
        for option in groups[pos]:
            path.append(option)
            backtrack(pos + 1)
            path.pop()

    backtrack(0)
    return result

Debugging clinic: read the symptom

A broken generator usually still returns something, and the shape of that something points at the bug. Every symptom below came from running the broken version:

The first row is aliasing. result.append(path) puts a reference to the one path list into result, so all six entries are the same object, which the final pops leave empty. It has nothing to do with how Python passes arguments; it's two names for one list. Advanced Recursion & Backtracking covers state bugs like this in depth.

Test against a trusted reference

A generator is easy to check, because itertools already knows the right answer. Compare the outputs as multisets of tuples:

import itertools
import random

def same_answers(got, want):
    return sorted(map(tuple, got)) == sorted(map(tuple, want))

def check(trials=300):
    for _ in range(trials):
        nums = [random.randint(0, 2) for _ in range(random.randint(0, 6))]
        want = set(itertools.permutations(nums))      # distinct arrangements
        got = permute_unique(nums)
        assert same_answers(got, want), nums          # also fails if got has repeats
    print("all matched")

The values are drawn from 0–2 on purpose, so duplicates are common. Lengths start at 0, so [] → [[]] gets tested too. The references for the other families are itertools.permutations(nums), itertools.combinations(items, k), combinations of every size r from 0 to n for subsets, and itertools.product(*groups).

⚠️ Don't sort the inner lists before comparing. With sorted(sorted(p) for p in got), the order inside each answer is erased, and that order is exactly what a permutation test must check. A broken permute that returns [[1, 2], [1, 2]] would pass against [[1, 2], [2, 1]]. Sort the outer list of tuples only.

Final round: no label on the problem

Real problems don't say which move they want. For each one, decide: what is chosen at each level, which choices are allowed, and when is a path an answer?

Challenge 1: the case switch

LeetCode 784: Letter Case Permutation. Given a string of letters and digits (length ≤ 12), return every string you can make by switching the case of each letter. "a1b2" gives ["a1b2", "a1B2", "A1b2", "A1B2"], in any order. Which move is this, and how many strings does a string with L letters produce?

def letter_case_permutation(s):
    result, path = [], []

    def backtrack(pos):
        if pos == len(s):
            result.append("".join(path))
            return
        ch = s[pos]
        options = [ch.lower(), ch.upper()] if ch.isalpha() else [ch]
        for option in options:
            path.append(option)
            backtrack(pos + 1)
            path.pop()

    backtrack(0)
    return result

Challenge 2: cut into palindromes

LeetCode 131: Palindrome Partitioning. Split a string (length ≤ 16) into pieces that are all palindromes, and return every way to do it. "aab" gives [["a", "a", "b"], ["aa", "b"]].

def partition(s):
    result, path = [], []

    def backtrack(start):
        if start == len(s):
            result.append(path[:])
            return
        for end in range(start + 1, len(s) + 1):
            piece = s[start:end]
            if piece == piece[::-1]:    # only palindromic pieces may be chosen
                path.append(piece)
                backtrack(end)          # the next piece starts where this one ended
                path.pop()

    backtrack(0)
    return result

Challenge 3: keep the order, drop the repeats

LeetCode 491: Non-decreasing Subsequences. Return every different non-decreasing subsequence with at least two elements (length ≤ 15, values from −100 to 100). [4, 6, 7, 7] gives 8 answers, among them [4, 6, 7, 7] and [7, 7].

def find_subsequences(nums):
    result, path = [], []

    def backtrack(start):
        if len(path) >= 2:
            result.append(path[:])
        seen = set()                    # values already tried at THIS level
        for i in range(start, len(nums)):
            if nums[i] in seen:
                continue
            if path and nums[i] < path[-1]:
                continue                # would break the non-decreasing order
            seen.add(nums[i])
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()

    backtrack(0)
    return result

Cheat sheet: problem → knobs

And before any of it: count the answers, check the count against the constraints, and ask whether the problem wants the list, the count, or just one answer.

Before moving on, pick one family and write it from a blank editor. Say what each level chooses, which choices are allowed, and when a path is an answer. Then state the invariant, the number of answers, the time and extra space, and the bug you would expect to make. If you can do that for permutations with duplicates and for Combination Sum, the rest are variations.

Next: String Permutations for next permutation, permutation-in-string and strings with repeated letters. Constraint Satisfaction takes the same machine to N-Queens, Sudoku and Word Search, where pruning does the heavy lifting. Dynamic Programming Mastery counts answers without listing them.