Permutations and Combinations

Permutations and combinations are two of the most common building blocks in recursive and backtracking algorithms. A permutation is an arrangement of items where order matters ([1, 2, 3] is different from [3, 2, 1]), while a combination is a selection of items where order does not matter ({1, 2} is the same choice as {2, 1}). Both show up constantly in interview problems — generating passwords, seating arrangements, subsets, lottery numbers, and search-space exploration in backtracking puzzles like N-Queens or Sudoku all reduce to one of these two ideas.

Overview: What Are Permutations and Combinations?

Imagine you have three friends, Alice, Bob, and Carol, and three chairs in a row. How many ways can you seat them? Since every seat is distinct, swapping Alice and Bob produces a genuinely different seating. This is a permutation problem: there are 3! = 6 possible seatings. Now imagine instead you only need to pick two of the three friends to go to a conference — sending Alice and Bob is the same outcome as sending Bob and Alice. This is a combination problem: order doesn’t matter, and there are 3 possible pairs.

Both permutations and combinations are naturally generated with backtracking: a recursive technique where you build a partial solution one choice at a time, recurse deeper, and then undo (“backtrack”) the last choice before trying the next option. The pattern is always: choose an option, explore by recursing, then un-choose it to try a sibling option. This choose-explore-unchoose loop is what lets a single path list be reused across the whole search instead of allocating a fresh list at every recursive call.

For permutations, at each recursive step you may pick any element that hasn’t been used yet, so the branching factor shrinks by one each level (n, then n-1, then n-2, …). For combinations, you additionally enforce an order constraint — you only look forward from the last index you picked — so that [1, 2] and [2, 1] are never both generated as separate results.

Time and Space Complexity

The complexity of generating all permutations or combinations is dominated by how many results exist, because each one must be built and copied into the output.

Operation Time Complexity Space Complexity (output) Why
All permutations of n items O(n! · n) O(n! · n) There are n! permutations, and each takes O(n) time to copy into the result list.
All combinations, choose k of n O(C(n, k) · k) O(C(n, k) · k) There are C(n, k) = n! / (k! (n-k)!) combinations, each of length k.
Recursion call stack — O(n) (permutations) or O(k) (combinations) The stack depth equals how many elements are currently chosen — at most n or k frames deep at once.

It’s worth internalizing why the count itself explodes so fast: for n = 10, 10! = 3,628,800. Any algorithm that must enumerate every permutation is fundamentally exponential (technically factorial, which grows even faster than exponential) in the input size — no clever trick reduces this, because the answer itself is that large. This is why permutation-generation problems in interviews usually have small n (often n ≤ 10). Combinations are more forgiving because C(n, k) is much smaller than n! when k is small relative to n.

Examples

Example 1: All Permutations of a List

This is the canonical backtracking template: track which indices are used, build up path, and record a copy of path whenever it reaches full length.

def permute(nums: list[int]) -> list[list[int]]:
    result: list[list[int]] = []
    path: list[int] = []
    used = [False] * len(nums)

    def backtrack() -> None:
        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.pop()
            used[i] = False

    backtrack()
    return result


nums = [1, 2, 3]
for p in permute(nums):
    print(p)

Output:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

Because the loop always scans indices from left to right and the input is already sorted, the six permutations come out in lexicographic order. Every recursive call to backtrack tries each still-unused number in turn, immediately recurses one level deeper, and only after that recursive call fully returns does it pop the number back off path and mark it unused again — freeing it up for the next sibling branch.

Example 2: Combinations (Choose k of n)

Combinations use a start parameter instead of a used array. By only recursing on indices ≥ start, we guarantee each subset is only ever built in one order — increasing index order — so no duplicates like [2, 1] alongside [1, 2] can appear.

def combine(n: int, k: int) -> list[list[int]]:
    result: list[list[int]] = []
    path: list[int] = []

    def backtrack(start: int) -> None:
        if len(path) == k:
            result.append(path[:])
            return
        for i in range(start, n + 1):
            path.append(i)
            backtrack(i + 1)
            path.pop()

    backtrack(1)
    return result


for combo in combine(4, 2):
    print(combo)

Output:

[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]

This matches C(4, 2) = 6. Notice the base case checks len(path) == k rather than reaching the end of the array — this is what limits results to exactly k elements instead of generating every subset.

Example 3: Unique Permutations with Duplicate Values

If the input has duplicate values, the naive permutation template produces duplicate results (e.g. two identical [1, 1, 2] entries from swapping the two 1s). The fix is to sort the input first, then skip a candidate value if an identical value at the previous index hasn’t been used yet in the current branch — this enforces that equal values are only ever placed in one relative order.

def permute_unique(nums: list[int]) -> list[list[int]]:
    nums_sorted = sorted(nums)
    result: list[list[int]] = []
    path: list[int] = []
    used = [False] * len(nums_sorted)

    def backtrack() -> None:
        if len(path) == len(nums_sorted):
            result.append(path[:])
            return
        for i in range(len(nums_sorted)):
            if used[i]:
                continue
            if i > 0 and nums_sorted[i] == nums_sorted[i - 1] and not used[i - 1]:
                continue
            used[i] = True
            path.append(nums_sorted[i])
            backtrack()
            path.pop()
            used[i] = False

    backtrack()
    return result


for p in permute_unique([1, 1, 2]):
    print(p)

Output:

[1, 1, 2]
[1, 2, 1]
[2, 1, 1]

Without the duplicate-skip check, this input would print six results (with repeats) instead of the three genuinely distinct arrangements — 3! / 2! = 3, since the two 1s are indistinguishable from each other.

How the Backtracking Algorithm Works, Step by Step

Let’s trace permute([1, 2]) by hand to see exactly how the choose-explore-unchoose pattern unfolds.

  1. Start: path = [], used = [False, False]. The loop begins at i = 0.
  2. Choose index 0 (value 1): used = [True, False], path = [1]. Recurse.
  3. Inside the recursive call: path has length 1, not yet equal to 2, so the loop runs again. i = 0 is skipped (already used). Choose index 1 (value 2): used = [True, True], path = [1, 2]. Recurse.
  4. Base case reached: len(path) == len(nums) is true, so [1, 2] is copied into result. Return.
  5. Unchoose index 1: back in the previous frame, path.pop() removes the 2, and used[1] resets to False. The inner loop has no more indices to try, so this frame also returns.
  6. Unchoose index 0: path.pop() removes the 1, used[0] resets to False. Back in the outermost call, the loop advances to i = 1.
  7. Choose index 1 (value 2) first this time: path = [2], then recurse and choose index 0 (value 1), giving path = [2, 1], which is recorded as a second result.
  8. Everything unwinds back to the empty path and the outer loop ends, having produced [1, 2] and [2, 1] — all 2! = 2 permutations.

The key insight is that path is a single shared list that is mutated in place throughout the entire search; the recursion tree is explored depth-first, and every branch cleans up after itself (via pop() and resetting used) before its sibling branch begins. This is what makes backtracking memory-efficient compared to building a brand-new list at every call.

Common Mistakes

Mistake 1: Appending the Live List Instead of a Copy

A very common bug is forgetting to copy path before appending it to result. Since path is mutated throughout the search (elements get popped off as the recursion backtracks), storing a reference to it means every entry in result ends up pointing to the same list — and by the time the algorithm finishes, that list is empty.

def permute(nums):
    result = []
    path = []

    def backtrack():
        if len(path) == len(nums):
            result.append(path)  # BUG: stores a reference, not a copy
            return
        for num in nums:
            if num in path:
                continue
            path.append(num)
            backtrack()
            path.pop()

    backtrack()
    return result


print(permute([1, 2, 3]))

This prints [[], [], [], [], [], []] — six entries, all referencing the same now-empty path list, because every path.pop() that runs afterward mutates all of them at once. The fix is to store a shallow copy, either with slicing or list():

result.append(path[:])   # or: result.append(list(path))

Mistake 2: Using a Mutable Default Argument for the Accumulator

It’s tempting to give the accumulator list a default value so it doesn’t need to be passed in explicitly. This is a classic Python trap: default argument values are evaluated once, when the function is defined, and then reused across every call — so the same list silently accumulates leftover state from previous calls.

def combine(n, k, start=1, path=[]):  # BUG: mutable default argument
    result = []
    if len(path) == k:
        return [path[:]]
    for i in range(start, n + 1):
        path.append(i)
        result.extend(combine(n, k, i + 1, path))
        path.pop()
    return result


print(combine(3, 2))
print(combine(3, 2))  # second call is contaminated by leftover state

The safe pattern is to default to None and create a fresh list inside the function body:

def combine(n: int, k: int) -> list[list[int]]:
    result: list[list[int]] = []
    path: list[int] = []

    def backtrack(start: int) -> None:
        if len(path) == k:
            result.append(path[:])
            return
        for i in range(start, n + 1):
            path.append(i)
            backtrack(i + 1)
            path.pop()

    backtrack(1)
    return result

Wrapping the recursive helper as a nested (“closure”) function like this, rather than passing path and result as parameters, sidesteps the mutable-default trap entirely, since a brand-new path and result are created every time the outer function is called.

Best Practices

  • For production code, reach for itertools.permutations(iterable) and itertools.combinations(iterable, r) instead of hand-rolling backtracking — they’re implemented in C, handle edge cases correctly, and return iterators (lazy, memory-efficient). Implement it from scratch (as in this lesson) to understand backtracking itself, and because interviewers often ask you to derive it.
  • Always copy the accumulator (path[:] or list(path)) before storing it in the result — never store a reference to a list that will keep being mutated.
  • For combinations, use a start index to enforce increasing order and avoid generating the same subset twice in different orders.
  • For permutations with duplicate values, sort first and add the not used[i - 1] guard to skip redundant branches — this also prunes the search tree, making it faster, not just correct.
  • Never give a recursive helper a mutable default argument (def f(x, acc=[])); default to None and initialize fresh inside the function, or use a nested closure that captures a freshly-created list.
  • Be mindful of n! growth — if n is larger than roughly 10–12, generating every permutation is almost certainly not the intended solution; look for a way to avoid full enumeration (e.g. counting, dynamic programming, or a smarter combinatorial formula).

Practice Exercises

  • 1. Letter Case Permutations: Given a string containing letters and digits, generate all strings you can create by transforming each letter into lowercase or uppercase (digits stay unchanged). For "a1b", the expected output set is {"a1b", "a1B", "A1b", "A1B"}. Hint: this is a backtracking problem where each letter position branches into two choices, and digit positions have only one choice.
  • 2. Combination Sum: Given a list of distinct positive integers and a target, find all unique combinations (numbers may be reused unlimited times) that sum exactly to the target. For candidates = [2, 3, 6, 7] and target = 7, the expected output is [[2, 2, 3], [7]]. Hint: pass the same start index (not start + 1) into the recursive call when a number can be reused.
  • 3. Subsets (Power Set): Given a list of distinct integers, generate all possible subsets (the power set), including the empty subset and the full list itself. For [1, 2, 3] there should be 2^3 = 8 subsets total. Hint: unlike the combinations example, every node in the recursion tree is itself a valid result — not just the leaves.

Summary

  • A permutation cares about order (n! total arrangements of n distinct items); a combination does not (C(n, k) = n! / (k!(n-k)!) ways to choose k of n items).
  • Both are generated with the backtracking pattern: choose an option, recurse to explore further, then un-choose (undo) before trying the next sibling option.
  • Permutations track a used array so each element is placed exactly once per arrangement; combinations track a start index so elements are only ever chosen in increasing order.
  • Time and space complexity for generating all results is O(n! · n) for permutations and O(C(n, k) · k) for combinations — the count of results dominates, and the recursion stack itself only uses O(n) or O(k) space.
  • Always store a copy of the accumulator in the result, never a live reference — and never give a recursive helper a mutable default argument.
  • To generate permutations of input with duplicate values without duplicate output, sort first and skip a value if its identical predecessor hasn’t been used yet in the current branch.
  • In real production code, prefer itertools.permutations and itertools.combinations over hand-written backtracking; write it by hand to learn the technique and for interviews.