Subsets and Combinations

Interviewer cue: “return all possible subsets”, “return all combinations of size k”, or “return all permutations” — these three problems share one decision tree. The only thing that changes is which choice you’re making at each node: include-or-exclude, pick-k-in-order, or arrange-every-element.

What you’ll learn

• Three ways to generate all subsets: cascading (iterative), backtracking, and bitmask.
• How subsets map onto the same choose/explore/unchoose template from the previous lesson.
• Generating combinations of a fixed size k.
• Why there are always exactly $2^n$ subsets and $n!$ permutations.

The cue

You are looking at subsets or combinations when…

• The problem says “all subsets”, “the power set”, “all combinations”, “choose k”, or “every way to pick” — LC 78, 90, 77, 39, 40, 216.
• Order does not matter: {1,2} and {2,1} are the same answer. That single sentence is what separates this page from permutations, and it is what a start index encodes.
• Elements may be skipped, unlike permutations where every element must be used.
• Constraints are tiny — n <= 20 at most, usually n <= 10. $2^n$ output is expected.

The reframe: every element faces one binary decision — in or out — so the answer set has $2^n$ members and the recursion is a binary tree of depth n. A start index is what stops you revisiting earlier elements, which is exactly what makes {1,2} and {2,1} the same branch rather than two.

Reach for something else when order does matter (permutations: used[], not start), when you only need the count of valid subsets rather than the subsets themselves (that is DP — subset-sum counts in $O(nS)$, not $2^n$), or when n exceeds ~20, where $2^n$ output is impossible regardless of how you generate it.

Subsets, three ways

1. Cascading — build up the answer iteratively

Start with just the empty subset. For each new number, take every subset found so far and make a copy with that number added — the result set doubles in size every step.

subsets_cascading.py

def subsets_cascading(nums):
    result = [[]]
    for num in nums:
        result += [subset + [num] for subset in result]   # duplicate + extend every existing subset
    return result
 
 
print(subsets_cascading([1, 2, 3]))

2. Backtracking — the include/exclude decision tree

Instead of building bottom-up, walk the decision tree top-down: at each element, either include it in the current path or don’t, and record the path at every node (not just the leaves) — every partial path is itself a valid subset.

subsets_backtracking.py

def subsets_backtracking(nums):
    results = []
    path = []
 
    def backtrack(start):
        results.append(path[:])          # every node in the tree IS a subset
        for i in range(start, len(nums)):
            path.append(nums[i])         # 1. CHOOSE: include nums[i]
            backtrack(i + 1)              # 2. EXPLORE
            path.pop()                     # 3. UNCHOOSE
 
    backtrack(0)
    return results
 
 
print(subsets_backtracking([1, 2, 3]))

3. Bitmask — one integer encodes one subset

Every subset of an n-element list corresponds to one of the 2^n n-bit numbers: bit i set means “include nums[i]”. Counting from 0 to 2^n - 1 visits every subset exactly once.

subsets_bitmask.py

def subsets_bitmask(nums):
    n = len(nums)
    result = []
    for mask in range(1 << n):               # 1 << n == 2 ** n
        subset = [nums[i] for i in range(n) if mask & (1 << i)]
        result.append(subset)
    return result
 
 
print(subsets_bitmask([1, 2, 3]))

Visual intuition

The include/exclude tree, drawn. Every leaf is one subset, and every level is one element’s decision:

recursionOne decision per level, 2^n leavesLC 78 · O(n · 2^n)

call stack

[]

1def subsets(nums):2    out, path = [], []3    def go(i):4        if i == len(nums):5            out.append(path[:])      # copy! path keeps mutating6            return7        path.append(nums[i])         # branch 1: include8        go(i + 1)9        path.pop()                   # UNDO — this is the backtrack10        go(i + 1)                    # branch 2: exclude11    go(0)12    return out

i0path[]

callStart with an empty path and index 0. Every node in this tree is a decision about one element: include it or do not.

Play‹›1/39⟲

Watch the path shrink on the way back up. That shrinking is path.pop() — omit it and the path grows forever, which is the single most common backtracking bug. Note also the [:] copy when recording: path is one mutating list, so storing it directly stores a reference that later empties.

recursionPruning: every red node is a branch abandoned earlyLC 39

call stack

7

1def combination_sum(candidates, target):2    out, path = [], []3    def go(i, remaining):4        if remaining == 0:5            out.append(path[:]); return6        if remaining < 0 or i == len(candidates):7            return                       # dead branch — prune8        path.append(candidates[i])9        go(i, remaining - candidates[i])  # reuse i: repeats allowed10        path.pop()11        go(i + 1, remaining)             # move past candidates[i]12    go(0, target)13    return out

remaining7path∅i0

callStart with the full target of 7. 7 still to make, candidates from index 0 onward.

Play‹›1/81⟲

Count the red nodes. Each is work avoided the moment the remainder went negative. Sorting the candidates first lets you prune even earlier by breaking out of the loop, which is the standard follow-up to this problem.

How it works: the include/exclude tree

diagram Subsets of [1, 2, 3]: every include/exclude choice, every node is an answer mermaid

  graph TD
    R["[]"] --> Y1["[1]"]
    R --> N1["[]"]
    Y1 --> Y1Y2["[1, 2]"]
    Y1 --> Y1N2["[1]"]
    N1 --> N1Y2["[2]"]
    N1 --> N1N2["[]"]
    Y1Y2 --> A["[1, 2, 3]"]
    Y1Y2 --> B["[1, 2]"]
    Y1N2 --> C["[1, 3]"]
    Y1N2 --> D["[1]"]
    N1Y2 --> E["[2, 3]"]
    N1Y2 --> F["[2]"]
    N1N2 --> G["[3]"]
    N1N2 --> H["[]"]

Three binary decisions (include or exclude each of 1, 2, 3) give $2^3 = 8$ leaves — exactly the 8 subsets of a 3-element set. This is the same tree shape as the permutations tree from the Backtracking lesson, just with a binary choice at each level instead of “which unused element next.”

Combinations: pick exactly k, in order

Combinations use the same start-index backtracking as subsets, but only record the path once it reaches length k — no shorter or longer paths are collected.

combinations_backtrack.py

def combinations(n, k):
    results = []
    path = []
 
    def backtrack(start):
        if len(path) == k:
            results.append(path[:])
            return
        for i in range(start, n + 1):
            path.append(i)             # 1. CHOOSE
            backtrack(i + 1)            # 2. EXPLORE
            path.pop()                  # 3. UNCHOOSE
 
    backtrack(1)
    return results
 
 
print(combinations(4, 2))   # every 2-element combination from 1..4

Letter Combinations of a Phone Number is the same idea, n-ary

Instead of a binary include/exclude choice, each position picks one of several letters mapped to a digit ('2' -> "abc", '3' -> "def", …). The recursion is identical — choose one option, recurse to the next position, unchoose — just with more than two branches per node.

Dry run

Subsets of [1, 2, 3], backtracking version. Indentation is recursion depth; every node is recorded, not just the leaves:

text

record []          start=0
  record [1]       start=1
    record [1,2]   start=2
      record [1,2,3]
    record [1,3]
  record [2]       start=2
    record [2,3]
  record [3]       start=3

Eight subsets — $2^3$ — in the order [] [1] [1,2] [1,2,3] [1,3] [2] [2,3] [3].

• results.append(path[:]) happens at the top of every call, before the loop. That is the whole difference from permutations, where the record happens only at a full-length leaf: here every partial path is already a valid answer.
• start is what forbids {2,1}. After choosing 2, the loop begins at index 2, so 1 can never be appended afterwards. Replace start with a used[] array and you get all $3! = 6$ orderings of each subset instead — the permutation machinery, applied to the wrong question.
• The bitmask version enumerates in a different order — [] [1] [2] [1,2] [3] [1,3] [2,3] [1,2,3], counting 000 to 111 — and produces exactly the same set. Bit i of the mask means “element i is in”. If a problem wants a specific order, pick the generator accordingly; if not, the bitmask version is a two-line loop with no recursion.

Duplicates (LC 90) — [1, 2, 2]. Sort first, then skip a repeat within the same loop level:

guard	output	verdict
if i > start and nums[i] == nums[i-1]	[] [1] [1,2] [1,2,2] [2] [2,2]	correct — 6 distinct subsets
if i > 0 and nums[i] == nums[i-1]	[] [1] [1,2] [2]	wrong — [1,2,2] and [2,2] vanish

• i > start, not i > 0. The rule is “do not start two sibling branches with the same value” — a repeated value is perfectly legal deeper in the same branch. i > 0 also blocks the deeper use, which silently drops every subset containing a repeat.
• Sorting is mandatory so equal values are adjacent; without it the comparison never fires.

Complexity

Generator	Count of results	Time to build them all
Subsets	$2^n$	$O(n \cdot 2^n)$ (each of the $2^n$ subsets can cost up to $O(n)$ to copy)
Combinations of size k	$\binom{n}{k} = \dfrac{n!}{k!(n-k)!}$	$O(k \cdot \binom{n}{k})$
Permutations	$n!$	$O(n \cdot n!)$

All three are worst-case exponential (or factorial) — there’s no way around it, since that’s the size of the output itself. The only lever you have is pruning partial paths that can’t lead anywhere valid (as in N-Queens, Sudoku, or a “subsets that sum to target” variant).

When to use it

• “Return all subsets” — any of the three approaches above; backtracking generalizes best to variants with extra constraints (duplicates, sum targets).
• “Return all combinations of size k” — the start-index backtracking template, stopping at length k.
• “Return all permutations” — the used-array backtracking template from the previous lesson.
• Whenever you see “subsets”, “combinations”, or “permutations” in a problem statement, it’s almost always this exact family of decision trees — the only real design decision is what counts as a valid leaf.

The variant map

Problem	Recorded when	The one thing that changes
LC 78 Subsets	at every node	the base template
LC 90 Subsets II (duplicates)	every node	sort, then skip i > start and nums[i] == nums[i-1]
LC 77 Combinations C(n, k)	when len(path) == k	prune when k - len(path) exceeds the elements remaining
LC 39 Combination Sum (reuse allowed)	when remaining == 0	recurse with i, not i + 1 — that is what permits reuse
LC 40 Combination Sum II (each used once)	when remaining == 0	recurse with i + 1, plus the LC 90 duplicate skip
LC 216 Combination Sum III	len(path) == k and remaining == 0	two conditions, both prunable
LC 1863 Sum of All Subset XOR Totals	every node	or skip enumeration: each bit appears in exactly half the subsets
Bitmask enumeration	—	for m in range(1 << n); bit i means element i is in. No recursion, different order
Subset-sum count / partition	—	not enumeration — that is $O(nS)$ DP
Permutations	at full length only	used[] instead of start; order matters

Pitfalls

• results.append(path) without the copy. path keeps mutating, so every stored subset ends up as the same emptied list. path[:] snapshots it.
• i > 0 instead of i > start in the duplicate skip. It blocks repeats anywhere, not just as sibling branches — [1,2,2] loses [1,2,2] and [2,2] and looks plausible while doing it.
• Forgetting to sort before the duplicate skip. The rule compares neighbours; unsorted input never triggers it.
• Using start for permutations or used[] for subsets. start forbids revisiting earlier elements, which is exactly right when order does not matter and exactly wrong when it does.
• Recursing with i + 1 in LC 39. Reuse requires passing i; i + 1 silently solves LC 40 instead.
• Recording only at the leaves for LC 78. Every node is a subset; recording at depth n alone yields just the full set.
• Enumerating when a count was wanted. “How many subsets sum to k” is $O(nS)$ DP, not $2^n$.
• n beyond ~20. $2^{20}$ is a million subsets and $2^{30}$ is a billion — no generator saves you, because the output is the bound.

Interview follow-ups

They ask	What they’re checking	The answer
“Why does a start index give combinations rather than permutations?”	The core distinction	Because it forbids revisiting earlier elements, so each subset is generated in exactly one order. Swap it for a used[] array and every ordering appears — that is the permutation machinery
“What is the complexity?”	Honesty about output size	$O(n \cdot 2^n)$: there are $2^n$ subsets and copying each costs up to $O(n)$. That is optimal, because the output itself is that large
“Handle duplicates”	The subtle guard	Sort, then skip i > start and nums[i] == nums[i-1] — do not start two sibling branches with the same value. i > 0 instead also blocks legitimate deeper reuse and drops solutions
“Do it without recursion”	Breadth	Bitmask: for m in range(1 << n), include element i when bit i is set. Or the cascading build — start with [[]] and double the list per element. Both are two lines and neither can blow a stack
“Combination Sum allows reusing an element”	One character	Recurse with i rather than i + 1. Passing i + 1 gives LC 40’s each-used-once semantics instead, and the two problems are otherwise identical
“Prune LC 77 (C(n, k))”	Whether you can spot dead branches	Stop when the elements remaining are fewer than k - len(path) — those branches can never reach length k. Cheap to add and it removes a large fraction of the tree
“Now just count the subsets that sum to a target”	Recognising the boundary	That is subset-sum DP in $O(nS)$, not enumeration. Counting does not require generating, and at n = 100 enumeration is impossible while the DP is instant
“n is 30”	Scale sense	$2^{30}$ is a billion subsets — the output cannot be produced, so the question must be asking for a count, an optimum, or a property. Meet-in-the-middle ($2^{n/2}$) is the usual escape when it really is about subsets

Practice — real LeetCode problems

The three questions that define the family: enumerate every subset, do it again with duplicates in the input, then enumerate combinations that hit a target with reuse allowed. All three graders sort the output, so any order is accepted.

LC 78 — Subsets · Medium

Problem. Given an array of distinct integers, return all possible subsets (the power set). No duplicate subsets, any order.

Constraints. 1 <= len(nums) <= 10, -10 <= nums[i] <= 10, all distinct.

Examples. [1,2,3] gives the 8 subsets from [] to [1,2,3] · [0] gives [[], [0]]

pch.exerciseTag pch.exerciseTitle

Editorial · approach, complexity, follow-ups

The include/exclude tree. Two branches per level, n levels, $2^n$ leaves — one per subset — so nothing is enumerated twice.

Time $O(2^n \cdot n)$: $2^n$ subsets, each copied in $O(n)$. Space $O(n)$ for the path, plus $O(2^n \cdot n)$ for the output. You cannot beat that output size, which is why n <= 10 in the constraints.

• path[:] is mandatory. Appending path itself stores a reference, and every stored “subset” ends up empty once the recursion unwinds. This is the number one bug in the entire backtracking family.
• The empty subset counts, and it comes out first from the skip-everything branch. Answers with $2^n - 1$ subsets have dropped it.
• The elements are distinct, which is the only reason no dedup logic is needed. Remove that guarantee and you get the next problem.

Two alternatives worth knowing. Cascading: start with [[]] and, for each number, append it to a copy of everything so far — iterative, no recursion, and very easy to write. Bitmask: for mask in range(1 << n), take element i whenever bit i of mask is set. That one makes the $2^n$ explicit and is the neatest answer when the interviewer asks for a non-recursive version.

Follow-ups you should expect: “Duplicates in the input (LC 90)?” — next. “Only subsets of size k (LC 77)?” — stop at depth k and prune when not enough elements remain. “Subsets summing to a target?” — add the running sum and prune; that is subset sum. “In lexicographic order?” — take the branch before the skip branch, on sorted input. “n = 30?” — a billion subsets; the question has to be counting or DP, not enumeration.

LC 90 — Subsets II · Medium

Problem. Same as above, but the input may contain duplicates. Return all possible subsets with no duplicate subsets.

Constraints. 1 <= len(nums) <= 10, -10 <= nums[i] <= 10.

Examples. [1,2,2] gives [[],[1],[1,2],[1,2,2],[2],[2,2]] — six, not eight · [0] gives [[], [0]]

pch.exerciseTag pch.exerciseTitle

Editorial · approach, complexity, follow-ups

The whole problem is one line of pruning, and getting the condition exactly right is what is being tested.

Sorting groups equal values. Then, at a given depth, choosing the second 2 when the first 2 was already tried at that same depth would produce a subset already generated — so skip it. But choosing the second 2 below the first one is legitimate; that is how [2,2] gets built. The condition i > start draws exactly that line: i == start is the first candidate at this depth and always allowed.

• i > start, not i > 0. With i > 0 you would forbid [2,2] entirely and return only 5 subsets for [1,2,2]. This is the discriminating detail, and [1,1,1] — which must give 4 subsets, not 8 and not 2 — is the case that catches it.
• Without sorting the rule does nothing useful: [2,1,2] never has its 2s adjacent, so both are taken and you get duplicates.
• Recording at every node is the other form of the same enumeration. It suits the start-index style, where the loop skips forward rather than branching twice.

An alternative that avoids the pruning argument entirely: count the occurrences of each distinct value, then for each value decide how many copies to take, 0 up to its count. That generates each multiset exactly once by construction, and it is the cleaner answer if you find the i > start rule slippery.

Time $O(2^n \cdot n)$ worst case, less when duplicates prune. Space $O(n)$ plus output.

Follow-ups you should expect: “Combination Sum II (LC 40)?” — the same line, plus a target. “Permutations II (LC 47)?” — same idea, but the skip is over used positions at the current depth. “Why sort rather than dedup with a set of tuples?” — a set works and is a fine fallback, but it costs memory and hashing, and it does not prune the search. “Duplicates and a size limit?” — combine with the depth bound from LC 77.

LC 39 — Combination Sum · Medium

Problem. Given an array of distinct integers and a target, return all unique combinations that sum to the target. The same number may be chosen an unlimited number of times. Two combinations are the same if they use the same multiset of numbers.

Constraints. 1 <= len(candidates) <= 30, 2 <= candidates[i] <= 40, 1 <= target <= 40.

Examples. candidates = [2,3,6,7], target = 7 gives [[2,2,3],[7]] · candidates = [2,3,5], target = 8 gives [[2,2,2,2],[2,3,3],[3,5]] · candidates = [2], target = 1 gives []

pch.exerciseTag pch.exerciseTitle

Editorial · approach, complexity, follow-ups

Unbounded selection with uniqueness enforced by construction rather than by deduplication — the idea worth taking away.

Passing i instead of i + 1 permits reuse. Passing i instead of 0 forbids going backwards, so every generated combination is non-decreasing. Since each multiset has exactly one non-decreasing arrangement, each is produced exactly once. No set, no sorting of results, no dedup pass.

Time $O(n^{T/m})$ in the worst case, where $T$ is the target and $m$ the smallest candidate — the tree is at most $T/m$ deep with up to $n$ branches per level. Small here because target <= 40 and every candidate is at least 2. Space $O(T/m)$ for the path, plus output.

• i, not i + 1. With i + 1 each number is used at most once and [2,2,3] disappears — you would answer just [[7]].
• i, not 0. With 0 you would emit [2,2,3], [2,3,2] and [3,2,2] as three separate answers.
• break, not continue. The array is sorted, so the first candidate that overshoots means all later ones do. continue is merely slower, not wrong — but say which you mean and why.
• Unreachable targets give []. [2] with target 1 is the check, and note every candidate is at least 2 by constraint, so odd targets can be unreachable.
• Sorting is what licenses the break. Without it you must use continue.

Follow-ups you should expect: “Each number at most once, with duplicates in the input (LC 40)?” — recurse with i + 1 and add the i > start skip from LC 90. “Exactly k numbers from 1-9 (LC 216)?” — bound the depth as well as the sum. “Just count the combinations (LC 518)?” — coin-change DP; enumerating is exponential while counting is polynomial, and knowing which the question wants matters more than either algorithm. “Count permutations (LC 377)?” — the same DP with the loops swapped. “Candidates could be 1?” — the constraint forbids it, and for good reason: a 1 makes the tree explode.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

6 problems

0 easy6 medium0 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

• ○17Letter Combinations of a Phone NumbermediumThe same recursion with an n-ary (not binary) choice per positionNeetCode 150LeetCode Top Interview 150
• ○40Combination Sum IImediumNeetCode 150
• ○46PermutationsmediumThe `used`-array template from the Backtracking lessonNeetCode 150LeetCode Top Interview 150
• ○77CombinationsmediumThe `start`-index template, stopping at length `k`LeetCode Top Interview 150
• ○78SubsetsmediumAny of the three techniques above, distinct elementsNeetCode 150
• ○90Subsets IImediumSame problem with **duplicate** elements; sort first and skip repeats at the same recursion depth to avoid duplicate subsetsNeetCode 150

Self-check

pch.quizTag Subsets and combinations — self-check

1. What does the `start` index actually enforce?

   A That the output is sorted B That earlier elements are never revisited — so each subset is generated in exactly one order, which is what makes {1,2} and {2,1} the same answer C That the recursion terminates D That duplicates are skipped
   pch.quizShowAnswer

   B — That earlier elements are never revisited — so each subset is generated in exactly one order, which is what makes {1,2} and {2,1} the same answer — Swap `start` for a `used[]` array and you get every ordering of every subset — the permutation machinery. That one choice is the whole difference between the two pages.

2. In LC 78, where is the subset recorded?

   A Only at depth n, when all elements have been decided B At the top of every call, before the loop — every partial path is already a valid subset C Only when the path is non-empty D After the loop finishes
   pch.quizShowAnswer

   B — At the top of every call, before the loop — every partial path is already a valid subset — That is the structural difference from permutations, which record only at full-length leaves. Recording at the leaves here would return just the full set.

3. For duplicates (LC 90), why `i > start` rather than `i > 0`?

   A They are equivalent B Because the rule is 'do not start two SIBLING branches with the same value' — a repeated value is legal deeper in the same branch, and `i > 0` blocks that too, silently dropping [1,2,2] and [2,2] C Because start is always 0 D Because i > 0 would skip the first element
   pch.quizShowAnswer

   B — Because the rule is 'do not start two SIBLING branches with the same value' — a repeated value is legal deeper in the same branch, and `i > 0` blocks that too, silently dropping [1,2,2] and [2,2] — Verified: on [1,2,2] the correct guard yields 6 subsets and `i > 0` yields 4. The output still looks plausible, which is what makes it dangerous.

4. Combination Sum (LC 39) allows reusing an element; LC 40 does not. What is the code difference?

   A A different base case B One character in the recursive call: `bt(i)` permits reuse, `bt(i + 1)` moves past the element — LC 40 additionally needs the duplicate skip C LC 39 uses a used[] array D LC 40 sorts and LC 39 does not
   pch.quizShowAnswer

   B — One character in the recursive call: `bt(i)` permits reuse, `bt(i + 1)` moves past the element — LC 40 additionally needs the duplicate skip — These two problems sit next to each other on LeetCode precisely because the distinction is one index. Knowing which is which under pressure is the point.

5. What is the complexity of generating all subsets, and is it optimal?

   A O(2^n), and it can be improved with memoisation B O(n · 2^n) — 2^n subsets, each costing up to O(n) to copy — and yes, it is optimal, because the output itself is that large C O(n²), since each element is decided once D O(n!) like permutations
   pch.quizShowAnswer

   B — O(n · 2^n) — 2^n subsets, each costing up to O(n) to copy — and yes, it is optimal, because the output itself is that large — No cache helps when the answer IS the bottleneck. That is also why n ≤ 20 in these problems, and why 'count them' variants are DP rather than enumeration.

6. The problem asks how many subsets sum to a target, with n = 100. Now what?

   A Enumerate the subsets and count B Subset-sum DP in O(nS) — counting does not require generating, and 2^100 subsets cannot be enumerated at all C Meet in the middle D Sort and use two pointers
   pch.quizShowAnswer

   B — Subset-sum DP in O(nS) — counting does not require generating, and 2^100 subsets cannot be enumerated at all — Recognising 'count' versus 'enumerate' picks the entire approach. Meet-in-the-middle (2^(n/2)) is the escape when the subsets themselves are genuinely needed and n is around 40.

Recall card

• Cue — “all subsets / power set / combinations / choose k”, where order does not matter and elements may be skipped. Tiny n.
• Template — backtrack(start): record path[:] at every node, then loop i from start, choose → recurse with i + 1 → un-choose.
• start is the whole design — it forbids revisiting earlier elements, which is what makes {1,2} and {2,1} one answer. Permutations use used[] instead.
• Duplicates — sort, then skip i > start and nums[i] == nums[i-1]. i > start, not i > 0.
• Combinations — record only when len(path) == k; prune when too few elements remain.
• Reuse allowed (LC 39) — recurse with i, not i + 1.
• Copy on record — path[:], always.
• Cost — $O(n \cdot 2^n)$ for subsets, $O(k \cdot C(n,k))$ for combinations. Optimal: the output is the bound.
• Alternatives — bitmask (for m in range(1 << n)) or cascading doubling, both iterative.
• Counting, not listing? That is DP, not this.

Recap

• Subsets have three equally valid implementations — cascading (iterative doubling), backtracking (include/exclude tree, record every node), and bitmask (count from 0 to 2^n - 1).
• Combinations and permutations are the same backtracking template with a different base case: combinations stop at length k; permutations track a used array instead of a start index.
• Counts are fixed by the problem itself: $2^n$ subsets, $\binom{n}{k}$ combinations, $n!$ permutations — all exponential or worse, so pruning is the only lever for speed on constrained variants.

Next: Top K Elements — when you don’t need everything sorted, just the k largest or smallest, a size-k heap beats generating and sorting the whole set in $O(n \log k)$.