Subsets and Permutations: One Backtracking Template

"Generate all subsets" and "generate all permutations" look like two problems, and they are usually taught as two solutions to memorise. They are one idea. Both walk a decision tree, both build an answer on a shared path, and both undo each choice on the way back up. The only difference is the question asked at each level — and that question decides whether you get 2ⁿ answers or n!.

The problem it solves

Given distinct values, list every subset (every way to choose some of them, order ignored) or every permutation (every order of all of them). These are the base cases of a family: combinations of size k, subsets that sum to a target, arrangements with constraints. All of them are search problems where the answer space is too irregular for a formula but small enough to walk.

The intuition

Picture the answer being built one decision at a time, on a single list called path:

• Subsets ask, for each item in turn, "is it in or out?" Two branches per level, n levels, so 2ⁿ leaves. The index only ever moves forward, which is why [1, 2] and [2, 1] cannot both appear.
• Permutations ask, for each position, "which unused value goes here?" The first level has n branches, the next n - 1, and so on: n! leaves. A used array is what stops a value appearing twice on one path.

Around every branch is the same three-beat rhythm: choose (append to the path), explore (recurse), un-choose (pop). Because the path is shared by every branch, the pop is not tidying up — it is what makes the next branch start from the right place.

A leaf is recorded as a copy of the path. The path is still going to change; the copy is the answer.

Watch it run

The animation draws the subset tree for two items. Each level offers a skip branch and a take branch. The left side leaves 1 out and produces [] and [2], the search un-chooses back to the root, and the right side produces [1] and [1, 2]. Four leaves for two items; a third item would hang a copy of the tree under each leaf.

The code

Both generators, written with the same shape so the difference is easy to see:

def subsets(nums):
    out, path = [], []
    def go(i):
        if i == len(nums):                 # every item decided: a leaf
            out.append(path[:])            # copy, the path keeps changing
            return
        go(i + 1)                          # branch 1: skip nums[i]
        path.append(nums[i])               # branch 2: take it
        go(i + 1)
        path.pop()                         # un-choose
    go(0)
    return out

def permutations(nums):
    out, path, used = [], [], [False] * len(nums)
    def go():
        if len(path) == len(nums):         # every position filled: a leaf
            out.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue                   # already on this path
            used[i] = True; path.append(nums[i])     # choose
            go()                                     # explore
            used[i] = False; path.pop()              # un-choose
    go()
    return out

print(subsets([1, 2, 3]))
# [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
print(permutations([1, 2, 3]))
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
print(len(subsets(list(range(10)))), len(permutations(list(range(7)))))
# 1024 5040

The subset order looks odd because the skip branch runs first. Swap the two branches and the output starts with [1, 2, 3] instead; the set of answers is the same.

Duplicate values are where most solutions break. With [1, 2, 2], the plain subset tree cannot tell the two 2s apart, so [2] comes out twice. The fix is the same for both problems: sort, so equal values sit side by side, then refuse to start a branch with a value that an earlier sibling at the same level already started with. For subsets this uses the other common template, where each node picks the next item to add and every node is itself a subset:

def subsets_dedup(nums):
    nums = sorted(nums)                    # equal values side by side
    out, path = [], []
    def go(start):
        out.append(path[:])                # every node is a subset
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue                   # same value, same level: already tried
            path.append(nums[i])
            go(i + 1)
            path.pop()
    go(0)
    return out

def permutations_dedup(nums):
    nums = sorted(nums)
    out, path, used = [], [], [False] * len(nums)
    def go():
        if len(path) == len(nums):
            out.append(path[:])
            return
        for i in range(len(nums)):
            if used[i] or (i > 0 and nums[i] == nums[i - 1] and not used[i - 1]):
                continue                   # take equal values in index order only
            used[i] = True; path.append(nums[i])
            go()
            used[i] = False; path.pop()
    go()
    return out

print(len(subsets([1, 2, 2])), subsets_dedup([1, 2, 2]))
# 8 [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]
print(len(permutations([1, 1, 2])), permutations_dedup([1, 1, 2]))
# 6 [[1, 1, 2], [1, 2, 1], [2, 1, 1]]

The permutation rule reads: a copy of a value may be placed only if the copy before it is already on the path. That forces equal values to appear in one fixed order, so each distinct arrangement is built exactly once.

All four functions are checked against itertools on 1,000 random lists of up to six values drawn from 0 to 3, so duplicates are common. For the deduplicated versions, the reference is the set of distinct results:

import itertools, random

def as_set(lists):
    return sorted(tuple(x) for x in lists)

random.seed(9)
ok = True
for _ in range(1000):
    nums = [random.randint(0, 3) for _ in range(random.randint(0, 6))]
    ok &= as_set(subsets(nums)) == as_set(
        c for r in range(len(nums) + 1) for c in itertools.combinations(nums, r))
    ok &= as_set(permutations(nums)) == as_set(itertools.permutations(nums))
    ok &= as_set(subsets_dedup(nums)) == sorted(
        {tuple(sorted(c)) for r in range(len(nums) + 1)
         for c in itertools.combinations(nums, r)})
    ok &= as_set(permutations_dedup(nums)) == sorted(set(itertools.permutations(nums)))
print(ok)                                  # True

The complexity

The output dominates. There are 2ⁿ subsets of average length n / 2, and copying each costs its length, so subsets take O(n · 2ⁿ) time. There are n! permutations of length n, so permutations take O(n · n!). Extra space beyond the output is the recursion depth and the path, O(n). No algorithm can beat these bounds, since it has to write every answer; the goal is to not do more than that — which is exactly what the duplicate rule achieves when values repeat.

Where it goes wrong

• Appending the path instead of a copy. Every stored answer is then the same list object, which is empty once the search finishes.
• Forgetting to un-choose. A missing pop or used[i] = False leaks one branch's choice into the next, and the output is quietly wrong rather than crashing.
• Deduplicating at the end. Converting results to a set works, but only after generating every duplicate. With many repeats that is far more work than skipping the branch.
• Unsorted input with the skip rule. The nums[i] == nums[i - 1] test only catches duplicates that are adjacent.

How to say it in an interview

"Both are backtracking over a decision tree with choose, explore, un-choose. For subsets each level decides one item, in or out, so there are 2ⁿ leaves; for permutations each level fills one position with an unused value, so there are n!. I record a copy at each leaf. With duplicates I sort and skip a value that a sibling at the same level already tried, so each distinct answer is built once. Time is proportional to the output, O(n · 2ⁿ) or O(n · n!)."

The permutation tree has its own animation in the permutations lesson, and N-Queens adds pruning to the same loop.