Skip to content

105 — Combination Sum II

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 4 revisions

105 — Combination Sum II

LeetCode 40 · Medium. Given a collection of candidate numbers candidates (which may contain duplicates) and a target integer target, return all unique combinations where the chosen numbers sum to target. Each number in candidates may only be used once in a combination. The solution set must not contain duplicate combinations.

🍽️ Intuition

This chapter fuses the two twists from its neighbors: like Combination Sum (102), you're searching for subsets that sum to a target; like Subsets II (104), the input can contain duplicate values that must not produce duplicate outputs. The reuse rule flips, too — each index can be used at most once now, so the recursion advances past i instead of staying on it, while still needing the same-level duplicate skip to avoid exploring the same value combination twice.

🚩 Pattern-Recognition Cue

"May contain duplicates" + "each number used once" + "sum to target" together mean you need all three moves at once: advance past a chosen index (no reuse), sort first, and skip identical values at the same recursion depth (no duplicate combinations) — plus the early break once a sorted candidate exceeds the remaining target.

🐢 Brute Force

Backtrack over indices with no reuse (start advances to i + 1) and no duplicate-skip logic at all — just collect every combination that sums to target, then dump the results into a Set to remove the duplicates that come from picking "the first 1" versus "the second 1" at different indices.

func combinationSum2BruteForce(_ candidates: [Int], _ target: Int) -> [[Int]] {
    var seen: Set<[Int]> = []
    var path: [Int] = []

    func backtrack(_ start: Int, _ remaining: Int) {
        if remaining == 0 {
            // Sort before inserting: candidates isn't sorted, so two index-subsets holding the
            // same values in a different relative order would otherwise dodge the Set dedup entirely.
            seen.insert(path.sorted())
            return
        }
        if remaining < 0 || start == candidates.count { return }

        for i in start..<candidates.count {
            path.append(candidates[i])
            backtrack(i + 1, remaining - candidates[i])   // i + 1: no reuse of the same index
            path.removeLast()
        }
    }

    backtrack(0, target)
    return Array(seen)
}

// smoke test
print(combinationSum2BruteForce([10, 1, 2, 7, 6, 1, 5], 8).count)   // 4
print(combinationSum2BruteForce([2, 5, 2, 1, 2], 5).count)          // 2

Big-O: worst case O(2^n) combinations explored, each one fully built and hashed into the Set — including combinations that are value-identical to ones already found, which get generated in full before being recognized as duplicates and discarded.

🚀 Optimal

Sort first, advance past i (no reuse), skip same-level duplicate values before recursing, and break early once a candidate exceeds the remaining target — all four pruning moves from this batch, combined.

func combinationSum2(_ 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: rest are only bigger
            if i > start && sorted[i] == sorted[i - 1] { continue }     // prune: duplicate sibling branch

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

    backtrack(0, target)
    return results
}

// smoke test — same cases as the brute force, deterministic order this time
print(combinationSum2([10, 1, 2, 7, 6, 1, 5], 8))   // [[1,1,6],[1,2,5],[1,7],[2,6]]
print(combinationSum2([2, 5, 2, 1, 2], 5))          // [[1,2,2],[5]]

Big-O: same O(2^n) worst-case combinatorial bound, but duplicate branches are skipped with an O(1) check before recursing, and oversized candidates are discarded with a break that eliminates the rest of the loop in one step — no generate-then-hash pass needed afterward.

🔑 The Key Insight

Reusing 102's "unlimited picks" logic here would be a real bug, not just a missed optimization — it would let a single physical 1 in the input be counted twice in one combination. Advancing to i + 1 fixes that. But advancing alone still leaves duplicate values at different indices free to each start their own, value-identical branch — which is exactly what 104's same-level skip closes off. Combination Sum II only works because both fixes are applied together: i + 1 for "each element once," and i > start && sorted[i] == sorted[i - 1] for "no duplicate combinations from duplicate values."

🔗 Related Chapters

  • DFS and Backtracking — the shared choose/recurse/un-choose skeleton, here combining the target-sum pruning from Combination Sum with the duplicate-skip from Subsets II.
  • Arrays and Strings — sorting up front is what turns both the "too big" check and the "duplicate sibling" check into cheap, local comparisons.

🧸 Memory Sentence

Combination Sum II is Combination Sum without reuse, plus Subsets II's duplicate-skip on top — sort once, and it pays for three separate prunes: too big, already used, and already tried at this level.

✅ Check Your Understanding

  1. If combinationSum2 accidentally called backtrack(i, ...) instead of backtrack(i + 1, ...), which specific test case above would start producing a wrong (too-large) result, and why?
  2. Trace combinationSum2([1, 1, 2], 3) by hand. Which combinations are found, and at what point does the same-level duplicate skip prevent a repeat?
  3. Both break (for oversized candidates) and continue (for duplicate values) appear in the same loop. Why is one a break and the other a continue — what would go wrong if they were swapped?

⬅️ Previous: Subsets II · Next: Word Search ➡️

Clone this wiki locally