Permutations and Combinations by Backtracking, in depth: decision trees, duplicates, combination sum, next permutation, the Heap algorithm and ranking

Permutations, combinations and subsets are the three enumeration problems behind a surprising amount of real work: generating test cases, trying feature subsets, scheduling small sets of jobs, brute-forcing a puzzle, or checking an optimised solution against an exhaustive one. They look simple, and the textbook solutions fit in ten lines, yet the variants trip people constantly: duplicates in the input, elements that may be reused, a fixed size k, a target sum, or a need to jump straight to the millionth arrangement without generating the first 999,999.

This article treats them as a family. It starts from the decision tree each one walks, gives a correct template for each variant in Python, works through the duplicate rule by hand, then moves past recursion to iterative next permutation, Heap's algorithm and ranking, where an arrangement is converted to and from its index. The general backtracking pattern and pruning techniques are covered in Backtracking, in depth; here the focus is the enumeration problems themselves and their cost.

One decision tree, three problems

Every enumeration problem in this family walks a decision tree. A node is a partial answer, an edge adds one element, and a leaf, or for subsets every node, is a complete answer. The variants differ only in which edges a node may take. Permutations may take any element not yet used, so the root has n children, the next level n minus 1, and the tree has n factorial leaves. Combinations of size k may take only elements after the last one chosen, which kills reorderings and leaves C(n, k) leaves. Subsets are combinations of every size at once.

The permutation decision tree for [1, 2, 3]: each level fixes one position from the elements still unused, and the six leaves are the six permutations.

This view gives the cost directly. Producing every permutation costs at least n times n factorial, because there are n factorial outputs of length n to write, and no clever algorithm can beat the size of its output. For n = 10 that is 36 million element writes, fine; for n = 13 it is about 81 billion, hopeless. Combinations are cheaper: C(20, 10) is 184,756. Before writing code, compute the output size. If it is too large, the answer is not a faster enumerator but a different algorithm, such as dynamic programming, sampling or ranking.

Permutations

The standard permutation generator keeps a used array and a path. At each level it tries every unused element, marks it, recurses and unmarks it. The output is in lexicographic order if the input is sorted, which is often useful.

def permutations(nums):
    out, path, used = [], [], [False] * len(nums)

    def go():
        if len(path) == len(nums):
            out.append(path.copy())          # copy: path keeps changing
            return
        for i, x in enumerate(nums):
            if used[i]:
                continue
            used[i] = True
            path.append(x)
            go()
            path.pop()                       # undo in reverse order
            used[i] = False

    go()
    return out

A second form swaps elements in place: position i is filled by swapping each candidate from i onwards into it, recursing on i + 1, and swapping back. It needs no extra arrays, but its output is not in lexicographic order, and the duplicate rule below is harder to apply to it. The most common bug in both forms is appending path itself instead of a copy, which leaves the result full of references to one list that ends up empty.

Combinations and combination sum

Combinations add a start index. Each call may choose only from positions at or after start, which is what prevents [2, 1] from appearing once [1, 2] has. A second, cheap pruning rule matters a lot in practice: if there are fewer remaining elements than slots still to fill, stop.

def combinations(n, k):
    """All k-element combinations of 1..n, in lexicographic order."""
    out, path = [], []

    def go(start):
        if len(path) == k:
            out.append(path.copy())
            return
        need = k - len(path)
        for x in range(start, n - need + 2):  # leave room for the remaining picks
            path.append(x)
            go(x + 1)
            path.pop()

    go(1)
    return out


def combination_sum(candidates, target, reuse):
    """Combinations of candidates summing to target; candidates are positive."""
    candidates = sorted(candidates)
    out, path = [], []

    def go(start, remaining):
        if remaining == 0:
            out.append(path.copy())
            return
        for i in range(start, len(candidates)):
            x = candidates[i]
            if x > remaining:
                break                        # sorted, so every later x is too big
            if not reuse and i > start and x == candidates[i - 1]:
                continue                     # skip equal siblings when values are limited
            path.append(x)
            go(i if reuse else i + 1, remaining - x)
            path.pop()

    go(0, target)
    return out

The single difference between reusable and single-use elements is the index passed down: i allows the same element again, i + 1 does not. Sorting buys two things: the early break once a candidate exceeds the remaining target, and adjacent duplicates for the skip rule. Subsets fall out of the same skeleton by recording path at every call instead of only at the leaves.

Handling duplicates without a set

When the input has repeated values, the generators above produce repeated outputs: [1, 1, 2] yields six permutations, of which only three are distinct. Deduplicating afterwards with a set works but wastes the whole repeated subtree and memory. The right fix is to never enter a subtree twice for the same value at the same level. Sort the input, then at each level skip an element if it equals the previous one and the previous one is not currently in use:

for i, x in enumerate(nums):              # nums is sorted
    if used[i]:
        continue
    if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
        continue                          # an equal value was already tried at this level
    ...

Trace it on sorted [1a, 1b, 2]. At the root, 1a is tried and its subtree yields [1, 1, 2] and [1, 2, 1]. Back at the root, 1a is now unused, so 1b equals its unused predecessor and is skipped: its subtree would repeat what 1a produced. Then 2 is tried and yields [2, 1, 1] once, because inside it 1b is again skipped while 1a is unused. Three outputs, no waste. The condition not used[i - 1] is what distinguishes the same level, where 1a was tried and released, from a deeper level, where 1a is on the current path and 1b is a legitimate next choice. Combinations use the simpler rule from combination_sum: i > start and equal to the previous value.

Beyond recursion: next permutation and the Heap algorithm

Recursion is not the only way, and often not the best one. The next permutation algorithm turns an arrangement into the next one in lexicographic order in place, with O(n) worst-case and O(1) amortised work and no recursion. It handles duplicates for free, producing each distinct permutation exactly once.

def next_permutation(a):
    """Rearrange a into the next lexicographic permutation; return False after the last."""
    i = len(a) - 2
    while i >= 0 and a[i] >= a[i + 1]:
        i -= 1                               # find the rightmost ascent
    if i < 0:
        a.reverse()                          # last permutation: wrap to the first
        return False
    j = len(a) - 1
    while a[j] <= a[i]:
        j -= 1                               # rightmost element larger than a[i]
    a[i], a[j] = a[j], a[i]
    a[i + 1:] = reversed(a[i + 1:])          # the suffix was descending; make it ascending
    return True

Take [1, 3, 5, 4, 2]. The rightmost ascent is 3 then 5, so i points at 3. The rightmost element larger than 3 is 4. Swapping gives [1, 4, 5, 3, 2], and reversing the suffix after position 1 gives [1, 4, 2, 3, 5], which is the next permutation. Because state is just the array, this generator can be paused, resumed, sharded across workers by starting points, or run as a lazy iterator in a test harness. C++ ships it as std::next_permutation.

Heap's algorithm is the other classic iterative-friendly generator. It produces each permutation from the previous one by a single swap, which is ideal when evaluating a permutation is expensive and can be updated incrementally from one swap, for example the length of a tour in a small travelling salesman instance. Its order is not lexicographic.

def heap_permutations(a, k=None):
    k = len(a) if k is None else k
    if k == 1:
        yield tuple(a)
        return
    yield from heap_permutations(a, k - 1)
    for i in range(k - 1):
        j = i if k % 2 == 0 else 0           # the parity rule makes every swap new
        a[j], a[k - 1] = a[k - 1], a[j]
        yield from heap_permutations(a, k - 1)

Ranking and unranking

Sometimes you need one arrangement, not all of them: the 500,000th permutation of ten items for a reproducible test, a random combination drawn uniformly, or a compact integer id for an ordering. Ranking maps an arrangement to its index in lexicographic order; unranking maps an index back. For permutations, the factorial number system does both. With n items, the first element determines which block of (n minus 1) factorial permutations you are in:

from math import factorial, comb

def unrank_permutation(items, r):
    items, out = sorted(items), []
    for i in range(len(items) - 1, -1, -1):
        idx, r = divmod(r, factorial(i))     # which block, and the offset inside it
        out.append(items.pop(idx))
    return out

def unrank_combination(n, k, r):
    """The r-th (0-based) k-combination of 0..n-1 in lexicographic order."""
    out, x = [], 0
    while k:
        count = comb(n - x - 1, k - 1)       # combinations that start with x
        if r < count:
            out.append(x)
            k -= 1
        else:
            r -= count
        x += 1
    return out

Worked example: the permutation of [a, b, c, d] with rank 9. Three factorial is 6, so 9 // 6 = 1 picks b, leaving offset 3. Two factorial is 2, so 3 // 2 = 1 picks the second of [a, c, d], which is c, leaving 1. One factorial is 1, so index 1 of [a, d] picks d, and a is last: [b, c, d, a]. Counting by hand confirms it is the tenth permutation. Ranking runs the same arithmetic backwards. Combined with a uniform random integer, unranking gives exactly uniform random permutations and combinations without bias, and the cost is polynomial in n even when n factorial does not fit in 64 bits, because Python integers are unbounded.

Engineering the enumerator

Turning these into production code raises a few recurring decisions.

Generate lazily. Return a generator rather than a list when callers might stop early, such as when searching for the first arrangement that passes a check. Lists of permutations exhaust memory long before CPU time becomes the issue.
Prune inside the tree, not after. If a constraint can reject a partial answer, check it before recursing. Filtering complete answers multiplies cost by the size of every rejected subtree. Grid and graph searches such as word search and Hamiltonian paths are the same idea with adjacency deciding which edges exist.
Use the library when it fits. Python's itertools.permutations and itertools.combinations are implemented in C and are lexicographic by input position. They do not deduplicate repeated values, so use the sorted skip rule or next permutation for multisets.
Guard the size. Compute n factorial or C(n, k) before starting and refuse, or switch to sampling, above a threshold. A job that silently tries to enumerate 14 factorial arrangements will run for hours before anyone notices.
Test against a slow oracle. For small n, compare your generator with itertools plus a set: same count, same set, no duplicates, expected order. Such property tests catch most off-by-one errors in start indices and pruning bounds.

Failure modes

Symptom	Cause	Fix
Result is a list of empty lists	appending path instead of a copy	append path.copy() or a tuple
Duplicate outputs with repeated input	no skip rule, or input not sorted	sort, then skip equal values at the same level
[1, 2] and [2, 1] both in combinations	loop starts at 0 instead of start	pass i + 1 and loop from start
Combination sum misses answers with repeats	passing i + 1 when reuse is allowed	pass i for reusable elements
Runs forever on modest input	output size is factorial	estimate first; rank, sample or use DP
Deep recursion error	Python recursion limit on long paths	iterate with next permutation or an explicit stack

What to do next

Before enumerating anything, compute the output size: n factorial, C(n, k) or 2 to the n, and decide whether enumeration is viable.
Implement the used-array permutation generator and the start-index combination generator from memory, then check them against itertools for n up to 6.
Add the duplicate rule and test it on [1, 1, 2] and [1, 1, 2, 2]; the counts should be 3 and 6.
Write combination sum in both reuse and single-use forms and confirm the index passed down is the only difference.
Implement next permutation and use it to iterate all distinct permutations of a multiset without recursion.
Implement unrank for permutations and combinations, and use it to draw uniform random samples for a test generator.
Convert one existing eager enumeration in your code to a generator with an explicit size guard.
Read the pruning and estimation sections of Backtracking, in depth before tackling a constrained variant.

Key takeaway: Permutations, combinations and subsets are one decision tree with different edge rules: unused elements, elements after a start index, or every node as an answer. Compute the output size before writing code, copy the path when recording an answer, sort and skip equal siblings to handle duplicates, and pass i or i + 1 to control reuse. Use next permutation for resumable iteration, Heap's algorithm for one-swap updates, and unranking when you need one arrangement or a uniform sample instead of all of them.