Subsets, Combinations & Target Sums

Subsets, combinations and target-sum problems are all selections where order doesn't matter. Each element is either in or out, so they share one shape: a loop that only looks forward from a start index. Change the base case and the recursive index, and the same loop produces all subsets, all size-k combinations, or all combinations that add up to a target.

The idea#

Looking only forward (from start to the end) is what stops [1, 2] and [2, 1] both appearing. Each selection is built in index order, so it has exactly one path in the tree. Three knobs then cover the whole family:

Base case: snapshot every node (subsets), only at size k (combinations), or only when the remaining target hits 0 (target sums).
Recursive index: pass i + 1 when each element can be used once, and i when it can be reused.
Duplicates in the input: sort, then skip a value equal to the previous sibling at the same level: if i > start and nums[i] == nums[i - 1]: continue.

The sibling skip only applies to i > start. The first copy of a value at each level is still used, so a selection that needs two equal values survives, while a repeat of the same selection doesn't.

For target sums, pass the remaining target (target - value) instead of a running sum, so the goal is remaining == 0. If the candidates are sorted, you can break as soon as one is bigger than the remaining target, because every later one is bigger too.

Copy-passing vs path and undo#

With the knobs set, you still have to decide how the current selection travels down the tree. There are two ways to carry it.

Style	How it looks	Extra memory
Copy-passing recursion	`find(lst + [x], i + 1)`	a new list at every level, $O(k \cdot n)$ for combinations
Path with append and pop	`path.append(x)`, recurse, `path.pop()`	one shared list, $O(k)$

Copy-passing is easy to get right because nothing needs undoing, but every frame holds its own copy. The path style reuses one list and copies it only at the base case.

Complexity#

The depth of the tree decides the cost, and for target sums the depth depends on the target, not on N.

	Each element once	With reuse
Logic	include or exclude once	include the same element many times
Tree depth	N	about T / M
Time	$O(N \cdot 2^N)$	$O(N^{T/M})$
Space (recursion + path)	$O(N)$	$O(T/M)$

Here T is the target and M the smallest candidate. With candidates = [2] and target = 20, N is 1 but the tree is 10 levels deep. Without reuse, a target-sum search is back to include-or-exclude per element: $O(2^N)$ leaves, each copied in up to $O(N)$ . Size-k combinations cost $O(k \cdot \binom{n}{k})$ : one leaf per combination, $O(k)$ to copy it.

How to spot it#

These cues point to this family.

"All subsets", "power set", "all combinations of k numbers".
"All unique combinations that sum to target".
"Each number may be used once" (i + 1) vs "unlimited times" (i).
Input with duplicates but answers must be unique.
Small N (about 20 or less) when you must list everything.

Template#

Here is the loop for target sums, with each of the three knobs marked in the comments.

sort candidates            # enables the break and the sibling skip
track(start, remaining):
    if remaining == 0:                  # goal (knob: base case)
        record a copy of path
        return
    for i from start to n - 1:
        if cands[i] > remaining: break  # sorted: later ones are bigger
        if i > start and cands[i] == cands[i - 1]:
            continue                    # same value as previous sibling
        append cands[i] to path
        track(i or i + 1, remaining - cands[i])   # knob: reuse or not
        pop from path
track(0, target)

Only the base case changes for the other two. For subsets, record at every node instead. For size-k combinations, record when the path has k items.

Pitfalls#

Most bugs here are about indices and undoing state.

Passing start + 1 instead of i + 1. It revisits earlier elements and creates duplicates.
Skipping duplicates with i > 0 instead of i > start. That also drops valid answers that use two equal values.
Forgetting to undo every piece of state. If a choice changes several things (counts, a running score), undo all of them, or pass the value as an argument so it never needs undoing.
return where you meant break or continue. Inside a helper loop over candidates, a return ends the whole call and silently skips every remaining choice.
Claiming $O(2^N)$ when reuse is allowed. With reuse, the depth is T / M, so it's $O(N^{T/M})$ .

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with Subsets, Combinations and Combination Sum.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Subsets

Every node is a subset, so record a copy on entry, before the loop. Recurse with i + 1. Time is $O(N \cdot 2^N)$ .

Hint: Subsets II

Sort, record at every node, and apply the sibling skip (i > start). Checking if path not in res also gives unique answers, but each check scans every result found so far.

Hint: Combinations

Stop at len(path) == k. Prune when there aren't enough numbers left: if k - len(path) (still needed) is more than n - start + 1 (still available), return.

Hint: Combination Sum

Reuse is allowed, so recurse with i. Sort and break when a candidate exceeds the remaining target. The cost is $O(N^{T/M})$ , not $O(2^N)$ .

Hint: Combination Sum II

Each candidate is used once (i + 1), and the input has duplicates. Sort and skip with i > start, so [1, 1, 6] survives while a second [1, 7] doesn't.

Hint: Combination Sum III

Pick exactly k digits from 1 to 9 that add to n. Stop at len(path) == k, and prune when the sum would overshoot.

Hint: Sum of All Subset XOR Totals

You don't need the subsets themselves. Carry the running XOR as the state: include the element (curr ^ nums[i]) or skip it, and add curr at each leaf.

Hint: Non-decreasing Subsequences

Order matters, so you can't sort to group duplicates. Keep a used set per level and skip a value already tried at this level. That replaces the costly path not in res check.

Hint: Maximum Score Words Formed by Letters

Each word is a take-or-skip choice limited by letter counts. Taking a word subtracts its letters and adds its score; after the recursive call, add the letters back and undo the score (or pass the score as an argument). First drop words that can't be formed even from the full letter pool. In the "can this word be formed?" check, use break or continue, not return.

Key takeaways#

Order doesn't matter, so loop forward from start.
i + 1 means use once; i means reuse.
Duplicates: sort, then skip a value equal to its previous sibling (i > start).
Pass the remaining target, and break once a sorted candidate is too big.
With reuse the cost is $O(N^{T/M})$ , because the depth is the target over the smallest candidate.

Core idea#

Subsets, combinations and target sums are selections where order does not matter. One loop that looks forward from start covers them all. Change the base case and the recursive index.

Key points#

Base case: snapshot every node (subsets), at size k (combinations), or at remaining == 0 (target sums).
Recurse with i + 1 to use each element once, and with i to reuse it.
Duplicates: sort, then skip if i > start and nums[i] == nums[i - 1]: continue.
Pass the remaining target. With sorted candidates, break once one is bigger than the remaining target.
Combinations of size k: return when k - len(path) is more than n - start + 1. Time is $O(k \cdot \binom{n}{k})$ .
Path with append and pop uses $O(k)$ memory. Copy-passing (lst + [x]) uses a new list at every level.
Input you cannot sort (Non-decreasing Subsequences): keep a used set per level.
Budget problems: undo every piece of state, such as letter counts and the score.

Complexity#

	Subsets	Combination Sum (reuse)
Tree depth	N	about T / M
Time	$O(N \cdot 2^N)$	$O(N^{T/M})$
Space	$O(N)$	$O(T/M)$

T is the target and M is the smallest candidate.

Template#

sort candidates
track(start, remaining):
    if remaining == 0: record a copy of path; return
    for i from start to n - 1:
        if cands[i] > remaining: break        # later ones are bigger
        if i > start and cands[i] == cands[i - 1]:
            continue                          # duplicate sibling
        append cands[i] to path
        track(i if reuse else i + 1, remaining - cands[i])
        pop from path

Pitfalls#

Passing start + 1 instead of i + 1. It creates duplicates.
Skipping duplicates with i > 0. That drops valid answers such as [1, 1, 6].
Writing return where you meant break or continue.
Claiming $O(2^N)$ for Combination Sum. With reuse, the depth is T / M.

Say it in an interview#

"Order does not matter, so the loop runs forward from start."
"i + 1 means use once, i means reuse, and sorted input makes duplicate siblings easy to skip."