Subsets and Combinations

Interviewer cue: “return all possible subsets”, “return all combinations of size kk”, 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-kk-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 kk.
Why there are always exactly $2^n$ subsets and $n!$ permutations.

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]))

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]))

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 nn-element list corresponds to one of the 2^n2^n nn-bit numbers: bit ii set means “include nums[i]nums[i]”. Counting from 00 to 2^n - 12^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]))

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]))

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 11, 22, 33) 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 startstart-index backtracking as subsets, but only record the path once it reaches length kk — 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

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

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 startstart-index backtracking template, stopping at length kk.
“Return all permutations” — the usedused-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.

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) <= 101 <= len(nums) <= 10, -10 <= nums[i] <= 10-10 <= nums[i] <= 10, all distinct.

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

Editorial · approach, complexity, follow-ups

The include/exclude tree. Two branches per level, nn 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 <= 10n <= 10 in the constraints.

path[:]path[:] is mandatory. Appending pathpath 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 maskmask in range(1 << n)range(1 << n), take element ii whenever bit ii of maskmask 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 kk (LC 77)?” — stop at depth kk 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 = 30n = 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) <= 101 <= len(nums) <= 10, -10 <= nums[i] <= 10-10 <= nums[i] <= 10.

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

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 22 when the first 22 was already tried at that same depth would produce a subset already generated — so skip it. But choosing the second 22 below the first one is legitimate; that is how [2,2][2,2] gets built. The condition i > starti > start draws exactly that line: i == starti == start is the first candidate at this depth and always allowed.

i > starti > start, not i > 0i > 0. With i > 0i > 0 you would forbid [2,2][2,2] entirely and return only 5 subsets for [1,2,2][1,2,2]. This is the discriminating detail, and [1,1,1][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][2,1,2] never has its 22s 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 > starti > 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) <= 301 <= len(candidates) <= 30, 2 <= candidates[i] <= 402 <= candidates[i] <= 40, 1 <= target <= 401 <= target <= 40.

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

Editorial · approach, complexity, follow-ups

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

Passing ii instead of i + 1i + 1 permits reuse. Passing ii instead of 00 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 <= 40target <= 40 and every candidate is at least 2. Space $O(T/m)$ for the path, plus output.

ii, not i + 1i + 1. With i + 1i + 1 each number is used at most once and [2,2,3][2,2,3] disappears — you would answer just [[7]][[7]].
ii, not 00. With 00 you would emit [2,2,3][2,2,3], [2,3,2][2,3,2] and [3,2,2][3,2,2] as three separate answers.
breakbreak, not continuecontinue. The array is sorted, so the first candidate that overshoots means all later ones do. continuecontinue is merely slower, not wrong — but say which you mean and why.
Unreachable targets give [][]. [2][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 breakbreak. Without it you must use continuecontinue.

Follow-ups you should expect: “Each number at most once, with duplicates in the input (LC 40)?” — recurse with i + 1i + 1 and add the i > starti > start skip from LC 90. “Exactly kk 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

#	Problem	Difficulty	The twist
78	Subsets	Medium	Any of the three techniques above, distinct elements
90	Subsets II	Medium	Same problem with duplicate elements; sort first and skip repeats at the same recursion depth to avoid duplicate subsets
77	Combinations	Medium	The `startstart`-index template, stopping at length `kk`
46	Permutations	Medium	The `usedused`-array template from the Backtracking lesson
17	Letter Combinations of a Phone Number	Medium	The same recursion with an n-ary (not binary) choice per position

Recap

Subsets have three equally valid implementations — cascading (iterative doubling), backtracking (include/exclude tree, record every node), and bitmask (count from 00 to 2^n - 12^n - 1).
Combinations and permutations are the same backtracking template with a different base case: combinations stop at length kk; permutations track a usedused array instead of a startstart 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 kk largest or smallest, a size-kk heap beats generating and sorting the whole set in $O(n \log k)$ .

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Subsets and Combinations

What you’ll learn

Subsets, three ways

1. Cascading — build up the answer iteratively

2. Backtracking — the include/exclude decision tree

3. Bitmask — one integer encodes one subset

How it works: the include/exclude tree

Combinations: pick exactly k, in order

Complexity

When to use it

Practice — real LeetCode problems

LC 78 — Subsets · Medium

LC 90 — Subsets II · Medium

LC 39 — Combination Sum · Medium

LeetCode problem set

Recap

Was this page helpful?