Subsets & Combinations

The universal backtracking template

Every backtracking solution — regardless of whether it generates subsets, permutations, or solves N-Queens — is the same three-step recursive shape:

Choose — add a candidate to the current partial solution (mutate state).
Explore — recurse into the next decision.
Un-choose — undo the mutation before trying the next sibling candidate.

def backtrack(path, choices):
    if is_complete(path):
        results.append(path[:])   # copy! see "Common pitfalls" below
        return
    for choice in choices:
        if not is_valid(choice):   # pruning — see the constraint-satisfaction subtopic
            continue
        path.append(choice)        # 1. choose
        backtrack(path, next_choices(choices, choice))  # 2. explore
        path.pop()                 # 3. un-choose

This is a depth-first traversal of an implicit decision tree: every node is a partial solution, every edge is a choice, and every leaf (or every node, depending on the problem) is a candidate answer. The tree is never materialized — you generate and discard branches as you walk them, which is exactly why backtracking uses only O(depth) extra space despite exploring an exponential number of paths.

The critical difference from a plain DFS/recursion you've used for tree traversal (see Trees) is step 3. A tree traversal doesn't need to "undo" anything because each recursive call operates on a fresh, disjoint subtree. Backtracking algorithms mutate shared, reused state (a running list, a visited set, a board) across every branch of the recursion, so you must explicitly restore that state to what it was before you go on to try the next sibling. Forget the undo, and sibling branches see leftover state from a branch that already returned.

The include/exclude decision tree for subsets

The cleanest way to internalize the template is the subset-generation problem: given [1, 2, 3], produce every possible subset. At each element, you have exactly two choices — include it in the current subset, or don't. That's a binary decision made once per element, so the decision tree has depth n and 2ⁿ leaves, each leaf being one subset.

def subsets(nums):
    res = []
    subset = []

    def dfs(i):
        if i == len(nums):
            res.append(subset[:])
            return
        # choice 1: include nums[i]
        subset.append(nums[i])
        dfs(i + 1)
        subset.pop()             # un-choose
        # choice 2: exclude nums[i]
        dfs(i + 1)

    dfs(0)
    return res

There's a second, equally common way to frame the same tree, using a start index instead of an include/exclude branch. Here, every node of the recursion (not just the leaves) represents a valid subset, and the "choices" at each level are "which not-yet-considered element do I add next":

def subsets(nums):
    res = []
    path = []

    def dfs(start):
        res.append(path[:])          # every node is a valid subset
        for i in range(start, len(nums)):
            path.append(nums[i])
            dfs(i + 1)                # only look forward — never revisit i
            path.pop()

    dfs(0)
    return res

Both are backtracking; they just partition the same search space differently. The start-index framing generalizes more directly to combinations, so it's the one worth defaulting to.

Combinations: subsets with a fixed size

"Choose k of n" (LeetCode calls this combine(n, k)) is the same start-index tree, but you only collect a path when it reaches length k, and you can prune early: if the number of remaining candidates is smaller than the number of slots still needed, that whole branch is dead.

def combine(n, k):
    res = []
    path = []

    def dfs(start):
        if len(path) == k:
            res.append(path[:])
            return
        needed = k - len(path)
        # prune: not enough numbers left in [start, n] to reach size k
        for i in range(start, n - needed + 2):
            path.append(i)
            dfs(i + 1)
            path.pop()

    dfs(1)
    return res

This pruning line is the first real example of what the constraint-satisfaction subtopic will lean on heavily: a cheap, local check that eliminates entire subtrees before you ever recurse into them.

Avoiding duplicate subsets when the input has duplicates

If nums can contain duplicates (e.g. [1, 2, 2]), the naive algorithm above produces the same subset multiple times — picking "the 2 at index 1" vs "the 2 at index 2" both yield the subset [1, 2]. The fix has two parts:

Sort the input first, so duplicate values become adjacent.
At each recursion depth, skip a candidate if it equals the previous candidate you already tried at that same depth (i.e., the previous sibling in the for loop, not the previous element in the array).

def subsets_with_dup(nums):
    nums.sort()
    res = []
    path = []

    def dfs(start):
        res.append(path[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue          # skip duplicate sibling at this depth
            path.append(nums[i])
            dfs(i + 1)
            path.pop()

    dfs(0)
    return res

The i > start condition is what makes this work: it says "only skip if this isn't the first element being tried at this depth." The first occurrence of a duplicate value at a given depth is always allowed through; only the second, third, ... occurrences at the same depth are skipped, because using the first one already explores every subtree that using a later identical copy would explore. Internalize this trick now — it reappears with a small but important twist in the Permutations subtopic.

Combination Sum: with and without reuse

"Combination Sum"-style problems (find combinations summing to a target) add a new axis: can the same element be reused within one combination?

Variant	Reuse allowed?	Recursive call after choosing `nums[i]`	Duplicate handling
Combination Sum	Yes, unlimited	`dfs(i, ...)` — stay at `i`	Input has no duplicates; not needed
Combination Sum II	No, each used once	`dfs(i + 1, ...)` — advance past `i`	Sort + skip-same-sibling trick (as above)

The entire difference between "with reuse" and "without reuse" is whether the recursive call passes i or i + 1 as the next start. This single-line difference is one of the highest-leverage things to get automatic before an interview — misremembering it silently produces either infinite recursion (reusing when you shouldn't advance) or missing valid combinations.

def combination_sum(candidates, target):
    res = []
    path = []

    def dfs(start, remaining):
        if remaining == 0:
            res.append(path[:])
            return
        if remaining < 0:
            return
        for i in range(start, len(candidates)):
            path.append(candidates[i])
            dfs(i, remaining - candidates[i])   # note: i, not i + 1 — reuse allowed
            path.pop()

    dfs(0, target)
    return res

Sorting candidates first also unlocks a pruning trick worth knowing: once candidates[i] > remaining, every subsequent candidate (being ≥ candidates[i] after sorting) is also too large, so you can break the loop entirely instead of just continue-ing past this one candidate.

Decision guide: subsets vs. combinations vs. permutations vs. combinations-with-repetition

Pattern	Order matters?	Fixed size?	Reuse element?	Branching per node	Total count
Subsets	No	No	No	2 (include/exclude) or shrinking range	2ⁿ
Combinations (`n` choose `k`)	No	Yes (`k`)	No	Shrinking range, `start → n`	C(n, k)
Combinations with repetition	No	Yes (`k`)	Yes	Shrinking range, `start` stays put on reuse	C(n + k − 1, k)
Permutations	Yes	Yes (`n`)	No	Full range minus used elements	n!

The mental shortcut: order matters → permutations (next subtopic); order doesn't matter → subsets/combinations, and within that family, whether you can revisit an element controls whether the recursive call advances start or not.

Complexity analysis

Subset-generation problems are O(2ⁿ) — there are exactly 2ⁿ subsets of an n-element set, and even if you don't explicitly enumerate them all (e.g. Combination Sum prunes on remaining < 0), the worst-case bound is still governed by the size of the decision tree, which is at most 2ⁿ nodes. Building each subset/combination costs an additional O(k) (or O(n)) to copy it into the result, so total time is typically stated as O(n · 2ⁿ) or O(k · C(n, k)).

This is precisely the exponential complexity class introduced in Big-O & Complexity Analysis: two recursive branches per level, n levels deep. Pruning (the remaining < 0 cutoff, the "not enough elements left" check in combine) does not change the worst-case asymptotic bound — in the worst case (e.g., all candidates are 1 and the target is large) you can still visit close to the full tree. What pruning changes is the practical, average-case runtime, often by orders of magnitude, by cutting off subtrees the moment they're provably dead rather than walking all the way to a leaf to discover that. State this distinction explicitly in an interview: "worst-case is still O(2ⁿ), but pruning means we almost never touch the full tree in practice."

Common pitfalls

Appending a reference instead of a copy. res.append(path) stores a reference to the same list object that keeps getting mutated by future append/pop calls — by the time you're done, every entry in res points to the same (now-empty) list. Always append path[:] (Python), new ArrayList<>(path) (Java), or the equivalent copy. This is the single most common backtracking bug, full stop.
Forgetting the un-choose step. If you path.append(x) and recurse but never path.pop() on the way back up, every subsequent sibling branch silently inherits x, corrupting all of your remaining output. This is the direct consequence of skipping step 3 of the template.
Skipping duplicates with the wrong condition. Writing nums[i] == nums[i - 1] without the i > start guard will (incorrectly) also block the first legitimate use of a repeated value at a new depth, silently under-generating your output. The guard specifically distinguishes "a duplicate sibling at this recursion level" from "a duplicate that's fine because it's the first choice at this level."
Mixing up reuse semantics. Passing i + 1 when you meant to allow reuse (or vice versa) is a one-character bug that either infinite-loops or drops valid answers — always say out loud "can I use this element again?" before writing the recursive call.
Not sorting before duplicate-skipping. The nums[i] == nums[i - 1] check only works if duplicates are adjacent, which requires a sort first. This connects directly back to the "hidden O(n log n) you forgot to account for" trap from Big-O & Complexity Analysis — sorting changes your overall complexity floor.

Further Resources (Optional)

Practice Problems

Interview relevancy:!!!Critical — must-have!!Important — highly recommended!Good to have~Niche — rarely asked

SubsetsMedium!!!2/520m
Letter Combinations of a Phone NumberMedium!!2/520m
CombinationsMedium!!!2/520m
Subsets IIMedium!!3/525m
Combination SumMedium!!3/525m
Combination Sum IIMedium!!3/525m
Generate ParenthesesMedium!!!3/525m
Palindrome PartitioningMedium!4/530m

Optional Practice (Extra Reps)

For once you've cleared the main set above and want more reps on this pattern. These don't count toward the roadmap's progress stats — solve them purely for your own benefit.

Combination Sum IIIMedium!2/520m
Apple DivisionCSES~3/525m