102 — Combination Sum

102 — Combination Sum

LeetCode 39 · Medium. Given an array of distinct positive integers candidates and a target integer target, return all unique combinations of candidates where the chosen numbers sum to target. The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one chosen number differs.

---

🍽️ Intuition

This is Subsets with two twists: instead of choosing each element at most once, you can reuse a number as many times as you like, and instead of recording every node, you only record the nodes whose running sum lands exactly on target. Reuse means the recursion can't simply move to start + 1 after picking candidates[i] — it has to stay at i, because picking 2 twice in a row is legal. The running sum is what turns this from "generate everything" into "generate only what could still work."

---

🚩 Pattern-Recognition Cue

"Find all combinations that sum to target" combined with "the same number may be chosen an unlimited number of times" is the signal: unlimited reuse means the branching factor doesn't shrink as you go deeper the way it does for Subsets or Permutations, so the running sum becomes the only thing standing between this search and infinite recursion — and the only thing worth pruning on.

---

🐢 Brute Force

Recurse without sorting candidates first and without stopping early when a candidate is obviously too large — every candidate at every level gets a full recursive call, and the only thing that stops a bad branch is discovering, one level deeper, that the running sum went negative.

func combinationSumBruteForce(_ candidates: [Int], _ target: Int) -> [[Int]] {
    var results: [[Int]] = []
    var path: [Int] = []

    func backtrack(_ start: Int, _ remaining: Int) {
        if remaining == 0 {
            results.append(path)
            return
        }
        if remaining < 0 || start == candidates.count { return }

        for i in start..<candidates.count {
            path.append(candidates[i])
            backtrack(i, remaining - candidates[i])   // same index: reuse is allowed
            path.removeLast()
        }
    }

    backtrack(0, target)
    return results
}

// smoke test
print(combinationSumBruteForce([2, 3, 6, 7], 7))         // [[2, 2, 3], [7]]
print(combinationSumBruteForce([2, 3, 5], 8).count)      // 3
print(combinationSumBruteForce([2], 1))                   // []

Big-O: roughly O(n^(t/m + 1)) where n is the candidate count, t is the target, and m is the smallest candidate — but every candidate at every level still triggers a full recursive call before the remaining < 0 check can discard it, even candidates that were obviously too large the moment they were chosen. O(t / m) recursion depth for space.

---

🚀 Optimal

Sort candidates first, then break out of the loop the instant a candidate exceeds remaining — since the rest of the sorted array is only larger, none of them could possibly work either, so there's no need to even make the recursive call to find that out.

func combinationSum(_ candidates: [Int], _ target: Int) -> [[Int]] {
    let sorted = candidates.sorted()
    var results: [[Int]] = []
    var path: [Int] = []

    func backtrack(_ start: Int, _ remaining: Int) {
        if remaining == 0 {
            results.append(path)
            return
        }

        for i in start..<sorted.count {
            if sorted[i] > remaining { break }   // prune: everything after is even bigger

            path.append(sorted[i])
            backtrack(i, remaining - sorted[i])
            path.removeLast()
        }
    }

    backtrack(0, target)
    return results
}

// smoke test — same cases as the brute force
print(combinationSum([2, 3, 6, 7], 7))         // [[2, 2, 3], [7]]
print(combinationSum([2, 3, 5], 8).count)      // 3
print(combinationSum([2], 1))                   // []

Big-O: same O(n^(t/m + 1)) worst-case bound, but the sorted break discards every remaining candidate at a given level in one step instead of one wasted recursive call per candidate — in practice, dramatically fewer dead branches are ever entered. O(t / m) recursion depth for space.

---

🔑 The Key Insight

Both versions rely on the same correctness check — remaining < 0 means this branch can't work — but when that check fires is the whole difference. The brute force discovers a candidate was too big only after choosing it and recursing one level deeper. The optimal version sorts first so that the moment one candidate is too big, every candidate after it in the loop is guaranteed to be too big as well, and break throws all of them away in one motion instead of paying for a doomed recursive call per candidate. That's pruning an entire subtree at once instead of pruning it one leaf at a time.

---

🔗 Related Chapters

• DFS and Backtracking — the same "choose, recurse, un-choose" skeleton, with start staying fixed on each recursive call instead of advancing, to allow reuse.
• Arrays and Strings — path grows and shrinks in place with append/removeLast throughout the search.

---

🧸 Memory Sentence

Combination Sum is Subsets with infinite reuse — stay on the same index to allow picking a number again, and sort first so one oversized candidate lets you throw away everything after it in a single break.

---

✅ Check Your Understanding

1. Why does backtrack(i, remaining - sorted[i]) pass i instead of i + 1 — and what would break if it passed i + 1 instead?
2. combinationSum([2], 1) returns []. Trace the call and explain exactly which line stops the recursion instead of looping forever.
3. Why does sorting candidates first make the if sorted[i] > remaining { break } pruning check valid? What would go wrong if you tried the same break on an unsorted array?

---

⬅️ Previous: Subsets · Next: Permutations ➡️