Backtracking Time Complexity: Subsets Are O(n·2^n). Permutations Are O(n·n!). Here's the Proof.

Every interview guide says subsets are O(2^n). Every LeetCode solution tab says it. Both are wrong, or at least incomplete. Getting backtracking time complexity right means accounting for a hidden factor of n, and missing it will cost you the moment an interviewer asks you to justify your analysis.

They're quoting the leaf count. Excellent. They forgot to multiply it by anything.

This is Part 2 of a series on recursion complexity. Part 1 covered how to read a recursion tree and derive a closed form from it. Here we apply those tools to the three tree shapes that appear in almost every backtracking problem: the binary subset tree, the n-ary permutation tree, and the start-index combination tree.

---

The emotional truth before the math. Our job: explain why O(2^n) and O(n!) are even worse than "O(no)" suggests.

---

Two Costs Live in Every Backtracking Problem

Backtracking pays two separate bills, and you need to count both.

The traversal cost is how many nodes you visit in the recursion tree. The copy cost is how much work you do when you reach a leaf and write the answer to your result list. Both get charged to the total.

Most complexity guides count only the first. The second is where the real growth hides. It's also the part your interviewer is waiting to hear.

---

The Subset Tree: Binary and Complete

Consider generating all subsets of [a, b, c]. At each position you make one binary choice: include this element or skip it. That is it. The recursion looks like this:

def subsets(nums):
    result = []

    def backtrack(index, path):
        result.append(path[:])   # copy, not reference
        for i in range(index, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return result

The recursion tree is a complete binary tree of height n. Every element is either in or out.

Each dashed edge skips an element; each solid edge takes it. The copy cost at each leaf equals the subset's length. Total: n·2^(n-1).

Counting nodes: at depth 0 you have 1 node, at depth 1 you have 2, at depth k you have 2^k. Summing depth 0 through n gives 2^(n+1) - 1 total nodes. The leaves number 2^n.

The traversal cost is O(2^n). That is what everyone quotes. Usually with the confident tone of someone who memorized it in 2019 and hasn't thought about it since.

Now the copy cost. When you reach a leaf and call path[:], you copy however many elements are in path at that moment. A leaf at depth k carries a subset of size k. There are C(n, k) such leaves. So the total copy work is:

total copy = Σ(k=0 to n)  k · C(n, k)

That sum has a closed form: n · 2^(n-1). Here is how you derive it. Start from the binomial theorem:

(1 + x)^n = Σ(k=0 to n)  C(n,k) · x^k

Differentiate both sides with respect to x:

n · (1 + x)^(n-1) = Σ(k=0 to n)  k · C(n,k) · x^(k-1)

Set x = 1:

n · 2^(n-1) = Σ(k=0 to n)  k · C(n,k)

One differentiation turns the leaf count into the copy cost. The left side after setting x=1 is exactly n·2^(n-1).

So the copy cost is O(n · 2^(n-1)) = O(n · 2^n). It dominates the traversal cost. The real time complexity for subsets is:

O(n · 2^n), not O(2^n).

---

The Permutation Tree: n-ary and Wide

Generating all permutations of [1, 2, 3] works differently. You pick one element for position 0 from all n choices, one for position 1 from the remaining n-1, and so on down to the last slot.

def permutations(nums):
    result = []

    def backtrack(path, used):
        if len(path) == len(nums):
            result.append(path[:])   # copy the complete permutation
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack(path, used)
            path.pop()
            used[i] = False

    backtrack([], [False] * len(nums))
    return result

The tree shape is very different from subsets.

Branching factor drops by one at each level. Six leaves, each copied at full length n. That's where O(n·n!) comes from.

Nodes at level k = n! / (n-k)! because you have chosen k elements already and there are (n-k)! orderings of the remaining ones. Call this P(n, k), the falling factorial. Summing all levels:

total nodes = Σ(k=0 to n)  n!/(n-k)!
            = n!/n! + n!/(n-1)! + ... + n!/1! + n!/0!
            = 1 + n + n(n-1) + ... + n!
            ≈ n! · e   (by the Taylor expansion of e)

The traversal cost is O(n!).

The copy cost is sharper to count. Every leaf is at depth n and carries a complete permutation of length n. There are n! leaves. Each copy takes O(n). Copy cost = n · n!.

That dominates the O(n!) traversal work. So:

Permutations run in O(n · n!) time, not O(n!).

That difference matters at n = 12. n! is 479,001,600. n · n! is 5,748,019,200. Your interviewer can tell the difference. So can your runtime.

---

The Combination Tree: Fixed Depth, Fewer Leaves

Combinations of size k from n elements use a start-index trick. After picking an element at index i, you only recurse into elements at indices greater than i. This prunes the tree aggressively.

def combinations(n, k):
    result = []

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

    backtrack(1, [])
    return result

The start-index rule cuts the tree asymmetrically. Picking 4 as the first element leaves nothing to pair it with, so that branch dies. Exactly C(n,k) leaves survive.

The leaves are exactly the C(n, k) valid combinations. Each leaf holds a path of length k, so copying it costs O(k).

The time complexity is O(k · C(n, k)).

The internal nodes add up to roughly C(n, 0) + C(n, 1) + ... + C(n, k-1), which is less than 2^n and always beaten by the leaf copy work for reasonable k. So the copy cost dominates here too.

---

Why the Copy Cost Always Wins

The pattern holds across all three:

Problem	Leaves	Copy per leaf	Total time
Subsets	2^n	average n/2	O(n · 2^n)
Permutations	n!	n	O(n · n!)
Combinations (size k)	C(n,k)	k	O(k · C(n,k))

In every case, the leaf count times the copy cost per leaf is the correct complexity. The traversal cost (visiting internal nodes) is strictly smaller.

Intuitively: every leaf represents one answer you must write out. Writing it costs proportional to its length. You cannot enumerate n! permutations faster than O(n · n!) because just writing them down takes that long.

This is an output-sensitive bound. The algorithm cannot outpace its own output.

---

Space Complexity: Two Separate Questions

Space complexity for backtracking splits into two questions that people often conflate.

Call stack depth. The recursion never goes deeper than the tree's height. For subsets and permutations that is O(n). For combinations of size k it is O(k). This is the in-flight working memory: the path array and the stack frames.

Output storage. If you collect all results in a list, you are storing every leaf. That is O(n · 2^n) for subsets, O(n · n!) for permutations, O(k · C(n,k)) for combinations of size k. This is often excluded from "space complexity" in interview answers, but you should flag it. For n=15 and permutations, storing all results needs roughly 15 · 15! ≈ 195 billion entries. That is not a list. That is a lifestyle choice.

The stack unwinds as backtracking proceeds, keeping only n frames alive at once. The result list is permanent and enormous. Both deserve a mention in your answer.

In an interview, state both. "The call stack is O(n). If we store all results, the output space is O(n · 2^n)."

---

The Insight: Tree Shape Determines the Leaf Count, Copy Length Determines the Cost

People memorize "subsets is 2^n, permutations is n!" and stop there. That gives you the leaf count. Nothing else. The actual time complexity requires multiplying by how much work you do at each leaf.

For subsets, that factor is the average subset length: n/2, which gives n · 2^n. For permutations, every leaf has the same length n, which gives n · n!. For combinations of size k, every leaf has length k, giving k · C(n,k).

The correct mental model: draw the tree, count the leaves, multiply by the copy cost per leaf. That is the real answer.

The copy bug and this complexity analysis are directly connected. The reason you must write path[:] in Python (not path) when appending to results is that you need to pay that O(k) copy cost. If you append the reference, all entries in result point to the same list. That list gets mutated on every backtrack step. Your result is now a beautiful collection of empty arrays, perfectly sorted by disappointment. The copy is not defensive coding. It is the actual O(k) work that belongs in your complexity analysis.

---

Backtracking Time Complexity: Quick Reference

• Subsets: binary decision tree of height n, 2^n leaves, O(n/2) average copy. Total: O(n · 2^n). Derived via d/dx of binomial theorem.
• Permutations: n-ary tree, n! leaves each of length n. Total: O(n · n!).
• Combinations (size k): start-index tree, C(n,k) leaves each of length k. Total: O(k · C(n,k)).
• Traversal cost (internal nodes) is always dominated by leaf copy cost.
• Space: O(n) call stack. Output storage is separate and enormous.
• The copy per leaf is not optional work you can optimize away. It is intrinsic to producing the output.

---

If you want to practice narrating these derivations out loud under time pressure, SpaceComplexity runs voice-based mock interviews where the interviewer will ask you to justify your complexity claims, not just state them.

For the underlying backtracking patterns these complexities belong to, the backtracking explainer covers the three tree shapes in implementation detail. For how recursive subproblems can share structure and collapse to polynomial time, the dynamic programming framework is the natural next read.

---

Further Reading

• Backtracking (Wikipedia)
• Binomial coefficient (Wikipedia)
• Generate all permutations of a given array (GeeksforGeeks)
• Power Set (GeeksforGeeks)
• Algorithms for Permutations and Combinations (UT Austin CS3343)