Subsets, Permutations & Combinations

The mental model: a decision tree you walk by hand

Forget the code for a second. You have [1, 2, 3] and want all subsets. Draw a tree where at each level you decide the fate of one element:

graph TD
    ROOT["[ ]"]
    A["[1]"]
    B["[ ]"]
    A1["[1,2]"]
    A2["[1]"]
    B1["[2]"]
    B2["[ ]"]
    A11["[1,2,3] ✓"]
    A12["[1,2] ✓"]
    A21["[1,3] ✓"]
    A22["[1] ✓"]
    B11["[2,3] ✓"]
    B12["[2] ✓"]
    B21["[3] ✓"]
    B22["[ ] ✓"]
    ROOT -->|include 1| A
    ROOT -->|skip 1| B
    A -->|include 2| A1
    A -->|skip 2| A2
    B -->|include 2| B1
    B -->|skip 2| B2
    A1 -->|include 3| A11
    A1 -->|skip 3| A12
    A2 -->|include 3| A21
    A2 -->|skip 3| A22
    B1 -->|include 3| B11
    B1 -->|skip 3| B12
    B2 -->|include 3| B21
    B2 -->|skip 3| B22
    style ROOT fill:#7c5cff,color:#fff
    style A11 fill:#00ff9d,color:#0a0a0f
    style A12 fill:#00ff9d,color:#0a0a0f
    style A21 fill:#00ff9d,color:#0a0a0f
    style A22 fill:#00ff9d,color:#0a0a0f
    style B11 fill:#00ff9d,color:#0a0a0f
    style B12 fill:#00ff9d,color:#0a0a0f
    style B21 fill:#00ff9d,color:#0a0a0f
    style B22 fill:#00ff9d,color:#0a0a0f

Eight leaves, three elements. That's 2³ = 8. Every element doubles the tree. This is where 2^n comes from — not from some abstract analysis but from the literal structure of the choices you're making.

The TELL that you need subsets or permutations: the problem asks you to generate or enumerate all something. Words like "all possible," "find every," "return a list of lists." That's the signal. If it says "how many" or "minimum/maximum," you almost certainly want dynamic programming instead — you don't need to materialize every branch, just count or optimize over them.

The universal template

Every variant shares this skeleton:

def backtrack(start, current, result, nums):
    result.append(list(current))   # collect — for subsets this is every node
    
    for i in range(start, len(nums)):
        current.append(nums[i])    # choose
        backtrack(i + 1, current, result, nums)  # explore
        current.pop()              # un-choose

That current.pop() at the end — the un-choose — is not cleanup. It's load-bearing. Without it, current accumulates every element you ever touched and every branch sees a corrupt state. The pop is what makes the same mutable list safely reusable across all branches of the tree.

The three variants specialize this skeleton in exactly two places: where you collect and what you pass as start.

Subsets (Power Set)

Collect at every node — the root (empty set) is a valid subset, and so is every intermediate node:

def subsets(nums):
    result = []
    
    def backtrack(start, current):
        result.append(list(current))   # collect here — before the loop
        
        for i in range(start, len(nums)):
            current.append(nums[i])    # choose
            backtrack(i + 1, current)  # explore — start at i+1 so we don't re-pick
            current.pop()              # un-choose
    
    backtrack(0, [])
    return result

# subsets([1, 2, 3]) → [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

The i + 1 passed to the recursive call is what prevents [2, 1] from showing up alongside [1, 2]. You're always looking forward in the array, never back. That's the mechanism that makes order not matter for subsets.

Complexity: O(n · 2^n). The 2^n is the number of subsets; the extra n is the cost of copying current into result at each node.

Combinations of size k

Same thing, but with a size guard that prunes once the current path is the right length:

def combine(n, k):
    result = []
    
    def backtrack(start, current):
        if len(current) == k:        # collect only at leaves of depth k
            result.append(list(current))
            return                   # prune — going deeper can't help
        
        # pruning optimization: stop early if we can't possibly fill k slots
        remaining = k - len(current)
        for i in range(start, n - remaining + 2):  # n+1 is exclusive upper bound
            current.append(i)
            backtrack(i + 1, current)
            current.pop()
    
    backtrack(1, [])
    return result

The n - remaining + 2 upper bound on the loop is worth understanding. If you need 2 more elements and you're at position 5 out of 5, it's impossible — so you can cut the loop short. This is a pruning trick that matters when k is close to n.

Complexity: O(k · C(n, k)) where C(n, k) is the binomial coefficient — the number of combinations.

Permutations

Here the structure changes. You can pick any unused element at each level, and the order matters. So you don't pass a start index — you restart from 0 every time and skip elements you've already used:

def permutations(nums):
    result = []
    used = [False] * len(nums)
    
    def backtrack(current):
        if len(current) == len(nums):  # leaf: complete arrangement
            result.append(list(current))
            return
        
        for i in range(len(nums)):     # consider every element
            if used[i]:
                continue
            used[i] = True             # choose
            current.append(nums[i])
            backtrack(current)         # explore
            current.pop()              # un-choose
            used[i] = False
    
    backtrack([])
    return result

# permutations([1, 2, 3]) → 6 arrangements

Notice the used array does the same job that start index did in subsets — it's the mechanism that prevents you from picking the same element twice. The difference is that start enforces a forward-only constraint (no going back), while used enforces a uniqueness constraint (no re-using, but any position is fair game).

Complexity: O(n · n!). There are n! leaves, each costs O(n) to copy.

The duplicate problem: when your input has repeats

This is where most people's implementations break silently. Given [1, 1, 2], a naive subset generator produces [1, 2] twice — once by picking the first 1, once by picking the second. The output looks wrong and the fix is not obvious at first.

The pattern: sort the input, then at each level of recursion, skip any element that's identical to the one you just processed at this same level.

def subsets_with_duplicates(nums):
    nums.sort()        # CRITICAL: must sort first
    result = []
    
    def backtrack(start, current):
        result.append(list(current))
        
        for i in range(start, len(nums)):
            # skip duplicates at the same recursion level
            if i > start and nums[i] == nums[i - 1]:
                continue
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()
    
    backtrack(0, [])
    return result

Why i > start and not just i > 0? Because you're only skipping duplicates within the current loop — the same element is fine at different levels of the tree. i == start means you're at the first iteration of this level's loop, so you always allow it. i > start with a matching value means you already processed an identical element at this level, and this branch would produce an exact duplicate subtree.

The sort is not optional. Without it, duplicates might not be adjacent, and the nums[i] == nums[i-1] check would miss them.

Same idea for permutations with duplicates:

def permutations_with_duplicates(nums):
    nums.sort()
    result = []
    used = [False] * len(nums)
    
    def backtrack(current):
        if len(current) == len(nums):
            result.append(list(current))
            return
        
        for i in range(len(nums)):
            if used[i]:
                continue
            # skip if same value as previous AND previous wasn't used in this path
            # (meaning we already explored the branch using nums[i-1] at this slot)
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue
            used[i] = True
            current.append(nums[i])
            backtrack(current)
            current.pop()
            used[i] = False
    
    backtrack([])
    return result

The not used[i-1] condition is subtle. It means: if the previous duplicate element is NOT in the current path, we've already tried placing it at this slot and explored that whole subtree — skip. If it IS in the current path, the two duplicates are at different positions and produce genuinely different permutations, so allow it.

Three worked problems

Problem 1: Subsets II (LeetCode 90)

Given an integer array that may contain duplicates, return all possible subsets without duplicates in the output.

def subsets_ii(nums):
    nums.sort()
    result = []
    
    def backtrack(start, current):
        result.append(list(current))
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()
    
    backtrack(0, [])
    return result

# Input: [1, 2, 2]
# Output: [[], [1], [1,2], [1,2,2], [2], [2,2]]

Why it works: The sort groups both 2s together. When the loop reaches the second 2 (i=2, start=1), nums[2] == nums[1] and 2 > 1, so we skip it. The first 2 already explored the [..., 2, ...] branch; no reason to do it again.

Problem 2: Combination Sum (LeetCode 39)

Given a list of distinct candidates and a target, find all combinations that sum to target. You may reuse elements.

This one has a twist: you CAN reuse the same element. So instead of passing i + 1, you pass i:

def combination_sum(candidates, target):
    candidates.sort()
    result = []
    
    def backtrack(start, current, remaining):
        if remaining == 0:
            result.append(list(current))
            return
        
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break              # sorted: nothing ahead can help, prune the rest
            current.append(candidates[i])
            backtrack(i, current, remaining - candidates[i])  # i not i+1: allow reuse
            current.pop()
    
    backtrack(0, [], target)
    return result

The break (not continue) at candidates[i] > remaining works because the input is sorted — if this element is too large, everything after it is larger too. That's a pruning win that turns a bad case from timeout to fast.

Problem 3: Permutations II (LeetCode 47)

Generate all unique permutations of a list that may contain duplicates.

{ "type": "recursion", "fn": "fibonacci", "n": 5, "title": "branching factor at each level — permutations branch n-wide, subsets branch 2-wide" }

The recursion tree above shows how a 5-wide branch at each level multiplies to n! leaves — compare that to the binary branching of subsets. For permutations with duplicates:

def permute_unique(nums):
    nums.sort()
    result = []
    used = [False] * len(nums)
    
    def backtrack(current):
        if len(current) == len(nums):
            result.append(list(current))
            return
        
        for i in range(len(nums)):
            if used[i]:
                continue
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue
            used[i] = True
            current.append(nums[i])
            backtrack(current)
            current.pop()
            used[i] = False
    
    backtrack([])
    return result

# Input: [1, 1, 2]
# Output: [[1, 1, 2], [1, 2, 1], [2, 1, 1]]  — 3 unique permutations, not 3! = 6

Complexity and where n hits the wall

Problem type	Solutions	Copy cost	Total
Subsets of n elements	2^n	O(n) per subset	O(n · 2^n)
Combinations (n choose k)	C(n,k)	O(k) per combo	O(k · C(n,k))
Permutations of n elements	n!	O(n) per perm	O(n · n!)

These are hard floors, not algorithmic inefficiencies. You can't generate 2^n subsets faster than O(2^n) — the output itself has that size. Backtracking is the right tool because it generates exactly what you need without preallocating the full product space.

The concrete limits that matter in practice:

• n ≤ 15 for subsets: 2^15 = 32,768 — trivial.
• n ≤ 20 for subsets: 2^20 ≈ 1 million — fine.
• n ≤ 25 for subsets: 2^25 ≈ 33 million — tight, will probably squeeze through.
• n ≤ 8 for permutations: 8! = 40,320 — trivial.
• n ≤ 10 for permutations: 10! = 3.6 million — fine.
• n ≤ 12 for permutations: 12! ≈ 479 million — risky.

If an interview problem says n ≤ 20 and asks for permutations, stop and re-read it. The intended solution is almost certainly bitmask DP, not enumeration.

Common pitfalls

Not popping after the recursive call. This is the single most common bug. You add to current, recurse, return — and forget to pop. Now every subsequent branch sees a polluted current. Run the function on [1, 2, 3] without the pop and you'll see it immediately.

Passing the wrong start index. For subsets and combinations, you pass i + 1 (forward-only). For combination sum where reuse is allowed, you pass i. Mixing these up produces either missing results or infinite recursion.

Forgetting to restore used[i] in permutations. Same class of bug as forgetting to pop — you mark an element as used, recurse, and forget to un-mark it. The next sibling branch incorrectly sees it as unavailable.

Applying the duplicate skip without sorting first. The nums[i] == nums[i-1] guard only works if duplicates are adjacent. [1, 2, 1] without sorting would have nums[2] == nums[0] but nums[2] != nums[1], so the skip fires on the wrong comparison. Sort first. Always.

Collecting only at the leaves for subsets. If you put result.append(list(current)) inside the if len(current) == n check, you only get the full-length subsets — that's a permutation-style collection. For the power set, every intermediate node is a valid subset and must be collected before the loop.

When NOT to use enumeration

The instinct to enumerate everything — subsets, permutations — is useful, but know when to resist it.

You want to…	Better approach
Count subsets summing to target	DP (0/1 knapsack variant)
Check if any subset sums to target	DP or graph BFS/DFS over states
Find k-th permutation without generating all	Factorial number system math
Number of valid arrangements (like N-queens count)	DP with bitmask
Largest/smallest valid subset	Greedy or DP

The tell: if you only need a number (a count, a bool, a minimum), you almost certainly don't need to materialize every solution. The decision tree still exists — DP just memoizes over it instead of walking every branch explicitly. See the backtracking article for the full comparison of when to prune vs. when to memoize.

The graph connection is also worth flagging. A graph traversal and backtracking over a decision tree are the same algorithm under different names — DFS with state restoration. If your "subsets" problem involves a grid, rooms, or nodes, the technique you're applying is literally the same code dressed in graph language.

The one-page cheat sheet

You're in an interview and the problem says "generate all." Here's the decision:

flowchart TD
    A["Generate all what?"]
    B["Unordered selections\n(subsets/combinations)"]
    C["Ordered arrangements\n(permutations)"]
    D["Pass start index i+1\nCollect at every node"]
    E["Use used[] array\nRestart loop from 0"]
    F{"Duplicates\nin input?"}
    G["Sort + skip:\nif i > start and nums[i] == nums[i-1]: continue"]
    H["Sort + skip:\nif i > 0 and nums[i] == nums[i-1]\n   and not used[i-1]: continue"]
    A --> B
    A --> C
    B --> D
    C --> E
    D --> F
    E --> F
    F -->|yes, subsets| G
    F -->|yes, perms| H
    style A fill:#7c5cff,color:#fff
    style G fill:#22d3ee,color:#0a0a0f
    style H fill:#22d3ee,color:#0a0a0f

That flowchart is the whole technique. The code is just the template plus one or two of those guards. Once you've internalized which guard to add for which variant, these problems go from "I need to think through this" to "let me write the template and plug in the right pieces."