Combinations and Subsets

Given the array [1, 2, 3], how many subsets does it have? The answer is eight: the empty set, three singletons, three pairs, and the full set itself. Every element is either included or excluded, so an array of $n$ elements has $2^n$ subsets. Generating all of them is one of the most fundamental backtracking problems, and the pattern it establishes extends directly to combinations, combination sums, and handling duplicates.

The Backtracking Framework: Include or Exclude

The idea is simple. Walk through the elements one by one. At each element, you have two choices: add it to your current path, or skip it. After making a choice, move on to the next element. When you have considered every element, whatever is in your path is one valid subset.

In practice we implement this as a recursive function that loops through the remaining elements. At each recursive call, we first record the current path as a valid subset, then try extending it by adding each element from the current position onward. After recursing with that element included, we remove it (backtrack) and move to the next element.

The critical parameter is start, the index from which we begin considering elements. When we include element at index i, we recurse with start = i + 1. This ensures we only look forward, never backward. Without this constraint, we would generate both [1, 2] and [2, 1] as separate subsets, but those are the same set. The start index is what enforces the "order does not matter" property.

Walking Through the Recursion Tree for [1, 2, 3]

Let us trace the full recursion tree. We call bt(0, []).

At the root, path is []. We record it as a subset. Then we loop i from 0 to 2.

When i = 0, we add 1 to get path [1]. We record [1]. Now we loop i from 1 to 2.

With i = 1 inside that call, we add 2 to get [1, 2]. Record it. Loop i from 2 to 2. Add 3 to get [1, 2, 3]. Record it. No more elements, so backtrack: remove 3, path is [1, 2]. Backtrack again: remove 2, path is [1].

With i = 2, we add 3 to get [1, 3]. Record it. No more elements. Backtrack: remove 3, path is [1]. Backtrack: remove 1, path is [].

Back at the root with i = 1, we add 2 to get [2]. Record it. Loop from 2. Add 3 to get [2, 3]. Record it. Backtrack through both.

Finally i = 2 at the root: add 3 to get [3]. Record it. Done.

The eight subsets, in the order they appear: [], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3].

Notice that every subset is generated exactly once, and they are produced in lexicographic order. The start index prevents any element from appearing before an element with a smaller index, which is exactly what eliminates duplicates.

Code: Subsets

For LeetCode 78, the code is:

def subsets(nums):
    res = []

    def bt(start, path):
        res.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            bt(i + 1, path)
            path.pop()

    bt(0, [])
    return res

The function records a copy of path at every node in the recursion tree, not just at the leaves. That is the defining characteristic of subset enumeration: every intermediate state is a valid answer.

Combinations of Size k

LeetCode 77 narrows the focus: suppose you do not want all subsets, but only those of a specific size. Given n = 4 and k = 2, you want all pairs from [1, 2, 3, 4]: there are C(4, 2) = 6 of them.

The structure is identical to subsets, but with one change: instead of recording path at every node, you only record it when len(path) == k. You are still using the same start-index loop, still backtracking, but you only collect leaf nodes at the target depth.

There is also a valuable pruning opportunity. If the number of remaining elements is smaller than the number of elements still needed, there is no way to reach length k, so you can stop early. Specifically, if n - i < k - len(path), you can break out of the loop. This prune can cut the search space dramatically when k is small relative to n.

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

    def bt(start, path):
        if len(path) == k:
            res.append(path[:])
            return
        for i in range(start, n + 1):
            if n - i + 1 < k - len(path):
                break
            path.append(i)
            bt(i + 1, path)
            path.pop()

    bt(1, [])
    return res

The pruning condition n - i + 1 < k - len(path) says: there are n - i + 1 elements from i to n, and we still need k - len(path) elements. If the former is less than the latter, stop immediately.

Combination Sum: Allowing Reuse

In the standard combination problem, each element can be used at most once, which is why we recurse with i + 1. But what if elements can be reused? LeetCode 39 explores exactly this: given candidates [2, 3, 6, 7] and target 7, find all combinations that sum to 7, where each number may be used unlimited times.

The only change is that when we include element at index i, we recurse with start = i instead of start = i + 1. This allows the same element to be chosen again. We stop recursing when the running sum exceeds the target.

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

    def bt(start, path, remaining):
        if remaining == 0:
            res.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                continue
            path.append(candidates[i])
            bt(i, path, remaining - candidates[i])
            path.pop()

    bt(0, [], target)
    return res

Notice the recursive call passes i, not i + 1. That single character is the difference between "use each element once" and "use each element any number of times." The start index still prevents generating [2, 3] and [3, 2] as separate answers.

Subsets II: Handling Duplicates

With LeetCode 90, the input contains duplicates, like [1, 2, 2], and the basic subsets algorithm would generate duplicate subsets. Both the 2 at index 1 and the 2 at index 2 would produce the subset [1, 2], for instance.

The fix has two parts. First, sort the array so that duplicates are adjacent. Second, within the loop at any recursion level, skip an element if it equals the previous element and the previous element was not chosen at this level. That is, skip nums[i] if nums[i] == nums[i - 1] and i > start.

The condition i > start is the key. When i == start, this is the first time we are considering this value at this level, so we must try it. When i > start, we already tried this same value earlier in the same loop iteration, and including it again would produce a duplicate subset.

Walking Through Subsets of [1, 2, 2]

After sorting, the array is [1, 2, 2]. Let us trace the recursion.

bt(0, []): Record []. Loop from i = 0.

i = 0: Add 1, path = [1]. Record [1]. Call bt(1, [1]).

Inside bt(1, [1]): i = 1, add 2, path = [1, 2]. Record [1, 2]. Call bt(2, [1, 2]).

Inside bt(2, [1, 2]): i = 2, add 2, path = [1, 2, 2]. Record [1, 2, 2]. No more elements. Pop to [1, 2].

Back in bt(1, [1]): pop to [1]. Now i = 2. nums[2] = 2 equals nums[1] = 2, and 2 > start (which is 1). Skip it. This is where the duplicate [1, 2] would have been generated again, and we prevent it.

Pop to []. Now i = 1: add 2, path = [2]. Record [2]. Call bt(2, [2]).

Inside bt(2, [2]): i = 2, add 2, path = [2, 2]. Record [2, 2]. Pop to [2].

Back at root, i = 2: nums[2] = 2 equals nums[1] = 2, and 2 > start (which is 0). Skip.

Final result: [], [1], [1, 2], [1, 2, 2], [2], [2, 2]. Six unique subsets, no duplicates.

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

    def bt(start, path):
        res.append(path[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue
            path.append(nums[i])
            bt(i + 1, path)
            path.pop()

    bt(0, [])
    return res

The Key Distinction: Subsets vs. Combinations

The structural difference between subsets and combinations is about when you collect results:

Subsets collect at every node. Every time the recursive function is called, the current path is a valid subset, so you record it immediately. The recursion tree has $2^n$ nodes, and every single one contributes an answer.

Combinations collect at leaf nodes only. You recurse until the path reaches a target length k, and only then do you record it. Internal nodes are just intermediate states on the way to a valid combination.

Both use the same backtracking skeleton with a start index. Both use the same deduplication trick when duplicates are present. The only difference is the placement of the "record this answer" line: at the top of the function (subsets) versus inside an if len(path) == k check (combinations).

Generate Parentheses

LeetCode 22 demonstrates that generating all valid combinations of n pairs of parentheses is a backtracking problem with a twist: instead of iterating over array elements, you track two counters: how many open parens and how many close parens you have placed so far. You can add an open paren as long as open < n, and you can add a close paren as long as close < open. When both counters reach n, you have a valid string.

This is still the same include-or-skip framework, but the "elements" are the two characters ( and ), and the validity constraints replace the start index.

def generate_parenthesis(n):
    res = []

    def bt(path, open_count, close_count):
        if len(path) == 2 * n:
            res.append("".join(path))
            return
        if open_count < n:
            path.append("(")
            bt(path, open_count + 1, close_count)
            path.pop()
        if close_count < open_count:
            path.append(")")
            bt(path, open_count, close_count + 1)
            path.pop()

    bt([], 0, 0)
    return res

The recursion tree is a binary tree where each node branches into at most two choices. The constraint close < open prunes all invalid prefixes, so every leaf is a valid arrangement. The total number of valid strings is the nth Catalan number.

Letter Combinations of a Phone Number

Consider LeetCode 17: given a string of digits from 2 to 9, return all possible letter combinations that the digits could represent on a phone keypad. Each digit maps to a fixed set of letters (2 → "abc", 3 → "def", and so on). The backtracking structure is straightforward: for each digit in the input, try every letter that digit maps to, then recurse on the remaining digits.

Unlike subsets where you choose to include or exclude each element, here you must choose exactly one letter per digit. The recursion depth equals the number of digits, and the branching factor is 3 or 4 at each level.

def letter_combinations(digits):
    if not digits:
        return []
    mapping = {
        "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
        "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz",
    }
    res = []

    def bt(idx, path):
        if idx == len(digits):
            res.append("".join(path))
            return
        for ch in mapping[digits[idx]]:
            path.append(ch)
            bt(idx + 1, path)
            path.pop()

    bt(0, [])
    return res

The index here is not a start index for choosing subsets. It is a position index that advances by exactly one each level. Every digit must be "used," so there is no skip option. The total output size is the product of the letter counts for each digit.

Word Break II

LeetCode 140 asks you to find all ways to segment a string into a space-separated sequence of dictionary words, given a string and a dictionary. This is backtracking with memoization: at each position in the string, try every dictionary word that matches the current prefix, then recurse on the remainder.

The key insight is that subproblems overlap: the suffix starting at position i can be reached from many different segmentations of the prefix. Caching the results for each starting position avoids recomputation.

def word_break(s, word_dict):
    word_set = set(word_dict)
    memo = {}

    def bt(start):
        if start in memo:
            return memo[start]
        if start == len(s):
            return [[]]
        results = []
        for end in range(start + 1, len(s) + 1):
            word = s[start:end]
            if word in word_set:
                for rest in bt(end):
                    results.append([word] + rest)
        memo[start] = results
        return results

    return [" ".join(words) for words in bt(0)]

Without memoization, this would revisit the same suffix from every path that reaches it. With memoization, each starting index is solved at most once. The total work depends on the number of valid segmentations, which can be exponential in pathological cases, but the memo ensures no redundant exploration.

Path with Maximum Gold

LeetCode 1219 presents a grid where each cell contains a non-negative integer representing gold. Find the maximum gold you can collect by starting from any non-zero cell and moving in four directions without revisiting a cell. This is DFS/backtracking on a grid rather than on an array.

The pattern is: try every non-zero cell as a starting point, then from each cell explore all four neighbors. Mark cells as visited by temporarily setting them to zero (the grid itself serves as the visited set). After exploring, restore the original value. Track the maximum gold collected across all paths.

def get_maximum_gold(grid):
    rows, cols = len(grid), len(grid[0])
    max_gold = 0

    def bt(r, c):
        nonlocal max_gold
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == 0:
            return 0
        gold = grid[r][c]
        grid[r][c] = 0  # mark visited
        best = 0
        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            best = max(best, bt(r + dr, c + dc))
        grid[r][c] = gold  # restore
        return gold + best

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] > 0:
                max_gold = max(max_gold, bt(r, c))
    return max_gold

This is the same backtracking pattern, make a choice, recurse, undo the choice, but applied to a 2D grid. Setting the cell to zero is the "mark visited" step, and restoring it is the backtrack step. The start index is replaced by spatial coordinates.

Maximum Length of Concatenated String with Unique Characters

Looking at LeetCode 1239, given an array of strings, find the maximum length achievable by concatenating a subset of them such that every character in the concatenation is unique. This is subset-style backtracking: for each string, decide to include it or skip it.

The twist is the constraint: you can only include a string if none of its characters conflict with characters already chosen. A bitmask is a compact way to track which of the 26 lowercase letters have been used.

def max_length(arr):
    # precompute bitmasks, discard strings with internal duplicates
    masks = []
    for s in arr:
        mask = 0
        for ch in s:
            bit = 1 << (ord(ch) - ord("a"))
            if mask & bit:
                mask = -1
                break
            mask |= bit
        if mask >= 0:
            masks.append((mask, len(s)))

    def bt(idx, used):
        if idx == len(masks):
            return 0
        # skip current string
        best = bt(idx + 1, used)
        # include current string if no conflict
        m, length = masks[idx]
        if used & m == 0:
            best = max(best, length + bt(idx + 1, used | m))
        return best

    return bt(0, 0)

The bitmask used plays the same role as the path in subset enumeration: it records what has been chosen so far. The used & m == 0 check is the feasibility test: if any bit overlaps, the string cannot be included. This is a direct application of the include-or-skip pattern from subsets, with a constraint check before including.

Complexity Analysis

For subsets, there are $2^n$ subsets of an array of $n$ elements, and each subset can be up to length n, so the total time is $O(n \cdot 2^n)$. The recursion depth is at most n, so the auxiliary space is $O(n)$ not counting the output.

For combinations of size k, the number of results is C(n, k), and each result has length k, so the total time is $O(k \cdot C(n, k))$. With pruning, the algorithm avoids exploring branches that cannot possibly yield results, making it significantly faster in practice than the worst case.

For combination sum with reuse, the complexity depends on the target value and the smallest candidate. In the worst case it can be exponential in the ratio target / min(candidates).

For all variants with duplicates, the sorting step adds $O(n \log n)$, but the duplicate skipping reduces the number of branches explored, often making the algorithm faster than the non-duplicate version despite the sort.

Recognizing this pattern

You're probably looking at combinations and subsets backtracking when:

• The problem asks you to enumerate all subsets, all k-combinations, or all combinations summing to a target.
• Input size is small, typically n ≤ 20, because the output is exponential.
• The order of elements within an answer does not matter, only the choice of which elements appear.
• You see phrases like "all possible", "every subset", "all unique combinations", or "powerset".

Common templates:

• Powerset (include/skip): recurse on index, choose to include or skip each element. Example: Subsets.
• k-combinations: recurse with a start index, pick one element per level until length k. Example: Combinations.
• Combination sum with reuse: keep the same start index on recursion to allow repeats. Example: Combination Sum.
• Dedup with sorted input: sort, then skip nums[i] == nums[i-1] at the same recursion level. Example: Subsets II.