Combinations and Combination Sum — The Start-Index Backtracking Pattern

Problem Statement#

LC 77 — Combinations. Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n]. Order within a combination does not matter.

LC 39 — Combination Sum. Given an array of distinct positive integers candidates and a target, return all unique combinations where the chosen numbers sum to target. The same number may be chosen unlimited times.

LC 40 — Combination Sum II. Same as LC 39 but each candidate may be used at most once and the array may contain duplicates. Each combination must be unique.

Constraints (LC 77): 1 <= k <= n <= 20. Constraints (LC 39 / 40): 1 <= candidates.length <= 30, 2 <= candidates[i] <= 50, target up to 500.

Example (LC 77):

Input:  n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

Example (LC 39):

Input:  candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]

Example (LC 40):

Input:  candidates = [10,1,2,7,6,1,5], target = 8
Output: [[1,1,6],[1,2,5],[1,7],[2,6]]

Why This Problem Matters#

Combination problems are the second pillar of backtracking interviews after subsets. The combinations explained here power real-world systems: building product bundles within a price target, picking a tournament squad of size k, generating quorum subsets in distributed consensus, and selecting features in machine learning. FAANG companies including Amazon, Google, Meta, and Microsoft regularly post LC 39 and LC 40 in onsite loops because they expose three skills at once: recursion fluency, deduplication reasoning, and pruning intuition.

What makes this problem set so instructive is the contrast between the three variants. LC 77 teaches the pure start-index template. LC 39 introduces unlimited reuse by recursing with the same index. LC 40 layers in deduplication for repeated candidates. By the time you can write all three from memory, you own the start-index pattern forever and you can recognize it the moment a future problem asks for "all combinations" or "all selections."

The Core Insight#

Combinations differ from permutations in one crucial way: order does not matter, so [1, 2, 3] and [3, 2, 1] are the same combination. To avoid emitting both, you only ever extend a partial combination by elements that come AFTER the last one you picked. This is the start-index pattern: each recursive call receives a start index, and the for-loop iterates i from start to n. After choosing candidates[i], you recurse with either i + 1 (no reuse) or i (reuse allowed).

The decision tree at each node has up to n - start children, where each child commits to a specific element at the current position. The path from root to any node represents a partial combination, and you append a copy to the result when the size hits k (LC 77) or when the remaining target hits zero (LC 39 / 40).

For LC 40 with repeated candidates, the deduplication rule is the same trick used in Subsets II and 3Sum: sort the array, then within a single recursive call, skip candidates[i] when i greater than start and candidates[i] == candidates[i-1]. The condition i greater than start is the load-bearing piece — it allows the FIRST occurrence at this level to be picked but skips subsequent equal-value siblings that would generate identical subtrees.

Pruning is what turns a brute-force backtrack into an interview-worthy solution. Sort candidates ascending and break out of the for-loop the moment candidates[i] greater than remaining — any later element is even larger, so no valid combination exists down that branch. This single break can shrink the search space by orders of magnitude on adversarial inputs.

Visual Dry Run#

LC 39 with candidates = [2, 3, 6, 7], target = 7. Tree (each node shows the chosen element and remaining target).

bt(start=0, current=[], remaining=7)
  i=0: pick 2 -> bt(0, [2], 5)
    i=0: pick 2 -> bt(0, [2,2], 3)
      i=0: pick 2 -> bt(0, [2,2,2], 1)
        i=0: 2 greater than 1, break (prune)
      i=1: pick 3 -> bt(1, [2,2,3], 0) -> RECORD [2,2,3]
      i=2: 6 greater than 3, break
    i=1: pick 3 -> bt(1, [2,3], 2)
      i=1: 3 greater than 2, break
    i=2: 6 greater than 5, break
  i=1: pick 3 -> bt(1, [3], 4)
    i=1: pick 3 -> bt(1, [3,3], 1)
      i=1: 3 greater than 1, break
    i=2: 6 greater than 4, break
  i=2: pick 6 -> bt(2, [6], 1)
    i=2: 6 greater than 1, break
  i=3: pick 7 -> bt(3, [7], 0) -> RECORD [7]

Two combinations recorded: [[2,2,3], [7]]. Notice how the start index pinned to i (not i+1) on the recursive call enables 2 + 2 + 3 — element 2 was reused twice without revisiting 2 again from a higher level.

Solution (Optimal)#

Python — full backtracking template#

# LC 77 — Combinations of size k from [1..n]
def combine(n: int, k: int) -> list[list[int]]:
    result = []
 
    def bt(start: int, current: list[int]) -> None:
        # Goal: combination of exactly k elements
        if len(current) == k:
            result.append(current[:])  # snapshot copy
            return
 
        # Pruning: stop when remaining slots can't be filled
        # Need (k - len(current)) more elements; only n - i + 1 available from i
        remaining_slots = k - len(current)
        max_start = n - remaining_slots + 1
 
        for i in range(start, max_start + 1):
            current.append(i)        # choose
            bt(i + 1, current)       # explore: i+1 = no reuse
            current.pop()            # unchoose (backtrack)
 
    bt(1, [])
    return result
 
 
# LC 39 — Combination Sum (unlimited reuse)
def combinationSum(candidates: list[int], target: int) -> list[list[int]]:
    candidates.sort()                # enable pruning by ascending order
    result = []
 
    def bt(start: int, current: list[int], remaining: int) -> None:
        if remaining == 0:
            result.append(current[:])
            return
 
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break                # pruning: sorted, all later are larger
            current.append(candidates[i])
            bt(i, current, remaining - candidates[i])  # i, not i+1 -> reuse
            current.pop()
 
    bt(0, [], target)
    return result
 
 
# LC 40 — Combination Sum II (no reuse, candidates may repeat)
def combinationSum2(candidates: list[int], target: int) -> list[list[int]]:
    candidates.sort()
    result = []
 
    def bt(start: int, current: list[int], remaining: int) -> None:
        if remaining == 0:
            result.append(current[:])
            return
 
        for i in range(start, len(candidates)):
            # Deduplicate at this recursion level only
            if i > start and candidates[i] == candidates[i - 1]:
                continue
            if candidates[i] > remaining:
                break
            current.append(candidates[i])
            bt(i + 1, current, remaining - candidates[i])  # i+1 -> no reuse
            current.pop()
 
    bt(0, [], target)
    return result

JavaScript#

// LC 77
function combine(n, k) {
    const result = [];
    const current = [];
 
    function bt(start) {
        if (current.length === k) {
            result.push([...current]);
            return;
        }
        const need = k - current.length;
        const maxStart = n - need + 1;
 
        for (let i = start; i <= maxStart; i++) {
            current.push(i);          // choose
            bt(i + 1);                // explore: no reuse
            current.pop();            // unchoose
        }
    }
    bt(1);
    return result;
}
 
// LC 39
function combinationSum(candidates, target) {
    candidates.sort((a, b) => a - b);
    const result = [];
    const current = [];
 
    function bt(start, remaining) {
        if (remaining === 0) {
            result.push([...current]);
            return;
        }
        for (let i = start; i < candidates.length; i++) {
            if (candidates[i] > remaining) break;   // prune
            current.push(candidates[i]);
            bt(i, remaining - candidates[i]);       // reuse: stay at i
            current.pop();
        }
    }
    bt(0, target);
    return result;
}
 
// LC 40
function combinationSum2(candidates, target) {
    candidates.sort((a, b) => a - b);
    const result = [];
    const current = [];
 
    function bt(start, remaining) {
        if (remaining === 0) {
            result.push([...current]);
            return;
        }
        for (let i = start; i < candidates.length; i++) {
            if (i > start && candidates[i] === candidates[i - 1]) continue;
            if (candidates[i] > remaining) break;
            current.push(candidates[i]);
            bt(i + 1, remaining - candidates[i]);   // no reuse
            current.pop();
        }
    }
    bt(0, target);
    return result;
}

Complexity#

Time bounds are pessimistic — pruning typically slashes them by huge constant factors in practice.

Common Mistakes#

1. Using i + 1 when reuse is allowed (LC 39). This emits [7] but never [2, 2, 3] because the same element can never be picked twice in one combination. Use i to allow reuse.
2. Using i instead of i + 1 for LC 40. This produces duplicates like [1, 1, 1, ...] from a single 1 candidate. Each LC 40 candidate is consumed once, so always advance.
3. Wrong dedup boundary i greater than 0 instead of i greater than start. The condition must be relative to the current recursive level — outer levels have already chosen the prior duplicate legitimately.
4. Forgetting to sort before pruning. The break-on-too-large optimization assumes ascending order. Without sorting, only the dedup-skip rule still works; the break is unsafe.
5. Returning the same list reference instead of a copy. result.append(current) shares the mutable list — every recorded combination ends up empty after backtracking. Always copy with current[:] or [...current].

Interview Tips#

• State the pattern out loud: "This is the start-index pattern. Order does not matter, so I only extend by elements after the last chosen index."
• Name the recurrence parameters: start (next index to consider), current (path so far), and either remaining (target left) or len(current) (depth).
• Show pruning explicitly. Sorting plus the break line is a 1-second add that earns major points and demonstrates production-quality thinking.
• Demo on a tiny input. Walk through n=3, k=2 or target=5, candidates=[2,3] to prove the trace is rock solid before scaling up.
• Mention space. Stack depth is bounded by k (LC 77) or target / min(candidates) (LC 39).

Follow-up Questions#

• Combinations with duplicates allowed in input (LC 40 with target up to 10000) — same algorithm; pruning becomes critical and a memoized version is sometimes asked.
• Count instead of enumerate — switch to DP. LC 377 Combination Sum IV (which is actually permutations, despite the name) is a classic DP follow-up.
• All combinations of size at most k — change the base case to len(current) less-than-or-equal k and record at every level.
• Non-decreasing factor decomposition — same start-index pattern with a multiplicative target.

Key Takeaways#

• The start-index pattern enumerates combinations without duplicates by only ever extending forward in the input array.
• i + 1 means "no reuse" and i means "reuse allowed" on the recursive call — a one-character switch between LC 39 and LC 77.
• Sort plus break-on-too-large is the single biggest pruning win and converts brute force into an interview-strength solution.
• For repeated candidates, dedup with i greater than start and candidates[i] == candidates[i-1] to skip equal-value siblings at the SAME level.
• Always snapshot current[:] when recording — backtracking will mutate the path on the way back up.
• Mastering LC 77, LC 39, and LC 40 unlocks dozens of related problems including factor combinations, change-making, expression building, and bundle generation.