40. Combination Sum II (Medium)

Problem

Given a collection of integers candidates (may contain duplicates) and a target, find all unique combinations that sum to target. Each number may be used at most once; the result must not contain duplicate combinations.

Example

candidates = [10,1,2,7,6,1,5], target = 8 → [[1,1,6], [1,2,5], [1,7], [2,6]]
candidates = [2,5,2,1,2], target = 5 → [[1,2,2], [5]]

LeetCode 40 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, all subsets, filter by sum, dedup

Generate the power set; keep subsets summing to target; dedup via canonical tuples.

def combination_sum2(candidates, target):
    from itertools import chain, combinations
    found = set()
    for r in range(1, len(candidates) + 1):
        for combo in combinations(candidates, r):
            if sum(combo) == target:
                found.add(tuple(sorted(combo)))
    return [list(t) for t in found]

Complexity

Time: $O(2^n · n log n)$ .
Space: same.

Exponential and wasteful.

Swift

final class Solution {
    private func normalized(_ values: [[Int]]) -> [[Int]] {
        values.sorted { $0.lexicographicallyPrecedes($1) }
    }

    func combinationSum2(_ candidates: [Int], _ target: Int) -> [[Int]] {
        let count = candidates.count; var unique = Set<[Int]>()
        for mask in 0..<(1 << count) { var sum = 0, values: [Int] = []; for index in 0..<count where mask & (1 << index) != 0 { sum += candidates[index]; values.append(candidates[index]) }; if sum == target { unique.insert(values.sorted()) } }
        return normalized(Array(unique))
    }
}

Approach 2: Backtracking with `start` index (no skip)

Standard start-based backtracking, but without duplicate handling, this produces duplicate combinations when the input has repeated values.

def combination_sum2(candidates, target):
    candidates.sort()
    result = []
    path = []

    def backtrack(start, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break
            path.append(candidates[i])
            backtrack(i + 1, remaining - candidates[i])
            path.pop()

    backtrack(0, target)
    # Dedup the output
    return list({tuple(x) for x in result})  # fix

Complexity

Time: exponential + $O(m log m)$ for dedup.
Space: exponential storage.

The dedup step is a symptom, fix it at the source.

Swift

final class Solution {
    private func normalized(_ values: [[Int]]) -> [[Int]] {
        values.sorted { $0.lexicographicallyPrecedes($1) }
    }

    func combinationSum2(_ candidates: [Int], _ target: Int) -> [[Int]] {
        let values = candidates.sorted(); var unique = Set<[Int]>()
        func search(_ start: Int, _ remaining: Int, _ current: [Int]) { if remaining == 0 { unique.insert(current); return }; if remaining < 0 { return }; for index in start..<values.count { search(index + 1, remaining - values[index], current + [values[index]]) } }
        search(0, target, []); return normalized(Array(unique))
    }
}

Approach 3: Sort + skip same-level duplicates (canonical)

Sort, then at each level skip indices whose value equals the previous one at the same level. Same template as Subsets II.

def combination_sum2(candidates, target):
    candidates.sort()                           # L1: O(n log n) sort
    result = []
    path = []

    def backtrack(start, remaining):
        if remaining == 0:
            result.append(path[:])              # L2: O(k) copy
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break                           # L3: O(1) prune
            if i > start and candidates[i] == candidates[i - 1]:
                continue                        # L4: O(1) skip same-level duplicate
            path.append(candidates[i])          # L5: O(1) push
            backtrack(i + 1, remaining - candidates[i])  # L6: recurse (i+1, no reuse)
            path.pop()                          # L7: O(1) pop

    backtrack(0, target)
    return result

function combinationSum2(candidates: number[], target: number): number[][] {
    candidates.sort((a, b) => a - b);           // L1: O(n log n) sort
    const result: number[][] = [];
    const path: number[] = [];

    function backtrack(start: number, remaining: number): void {
        if (remaining === 0) {
            result.push([...path]);              // L2: O(k) copy
            return;
        }
        for (let i = start; i < candidates.length; i++) {
            if (candidates[i] > remaining) break;                         // L3: O(1) prune
            if (i > start && candidates[i] === candidates[i - 1]) continue; // L4: skip same-level dup
            path.push(candidates[i]);                                     // L5: O(1) push
            backtrack(i + 1, remaining - candidates[i]);                  // L6: recurse (no reuse)
            path.pop();                                                   // L7: O(1) pop
        }
    }

    backtrack(0, target);
    return result;
}

func combinationSum2(candidates []int, target int) [][]int {
    sort.Ints(candidates)              // L1: O(n log n) sort
    result := [][]int{}
    path := []int{}

    var backtrack func(start, remaining int)
    backtrack = func(start, remaining int) {
        if remaining == 0 {
            cp := make([]int, len(path))
            copy(cp, path)
            result = append(result, cp) // L2: O(k) copy
            return
        }
        for i := start; i < len(candidates); i++ {
            if candidates[i] > remaining {
                break                                           // L3: O(1) prune
            }
            if i > start && candidates[i] == candidates[i-1] {
                continue                                        // L4: O(1) skip same-level duplicate
            }
            path = append(path, candidates[i])                 // L5: O(1) push
            backtrack(i+1, remaining-candidates[i])            // L6: recurse (no reuse)
            path = path[:len(path)-1]                          // L7: O(1) pop
        }
    }

    backtrack(0, target)
    return result
}

Where the time goes, line by line

Variables: n = len(candidates), k = average solution length.

Line	Per-call cost	Times executed	Contribution
L1 (sort)	$O(n log n)$	1	$O(n log n)$
L3 (prune)	$O(1)$	pruned nodes	$O(pruned)$
L4 (skip dup)	$O(1)$	dup nodes	$O(dup)$
L6 (recurse)	$O(1)$ dispatch	surviving nodes	$O(2^n)$ ← dominates

Sorting enables both L3 (early termination) and L4 (same-level duplicate skip). The i > start guard is critical: it allows the same value to be chosen at different recursion levels while forbidding it at the same level.

Complexity

Time: $O(2^n)$ worst case; pruning and skip make it much faster in practice.
Space: $O(k)$ recursion, where k = average solution length.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Swift

final class Solution {
    private func normalized(_ values: [[Int]]) -> [[Int]] {
        values.sorted { $0.lexicographicallyPrecedes($1) }
    }

    func combinationSum2(_ candidates: [Int], _ target: Int) -> [[Int]] {
        let values = candidates.sorted(); var result: [[Int]] = []
        func search(_ start: Int, _ remaining: Int, _ current: [Int]) { if remaining == 0 { result.append(current); return }; var previous: Int?; for index in start..<values.count { let value = values[index]; if value > remaining { break }; if value == previous { continue }; previous = value; search(index + 1, remaining - value, current + [value]) } }
        search(0, target, []); return normalized(result)
    }
}

Summary

Approach	Time	Space
Powerset + filter + dedup	$O(2^n · n log n)$	$O(2^n)$
Backtracking + post-dedup	exponential	exponential
Sort + skip same-level	$O(2^n)$ with pruning	$O(k)$

The skip-same-level template (shared with Subsets II) is the right abstraction for “no duplicates allowed when input has duplicates.”

Test cases

def combination_sum2(candidates, target):
    candidates.sort()
    result = []
    path = []
    def backtrack(start, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break
            if i > start and candidates[i] == candidates[i - 1]:
                continue
            path.append(candidates[i])
            backtrack(i + 1, remaining - candidates[i])
            path.pop()
    backtrack(0, target)
    return result

def _run_tests():
    r = combination_sum2([10, 1, 2, 7, 6, 1, 5], 8)
    assert sorted(map(tuple, r)) == sorted([tuple([1,1,6]), tuple([1,2,5]), tuple([1,7]), tuple([2,6])])
    r2 = combination_sum2([2, 5, 2, 1, 2], 5)
    assert sorted(map(tuple, r2)) == sorted([tuple([1,2,2]), tuple([5])])
    # no solution
    assert combination_sum2([1, 2], 10) == []
    # single element solution
    assert combination_sum2([3, 3], 3) == [[3]]
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function combinationSum2(candidates: number[], target: number): number[][] {
    candidates.sort((a, b) => a - b);
    const result: number[][] = [];
    const path: number[] = [];
    function backtrack(start: number, remaining: number): void {
        if (remaining === 0) { result.push([...path]); return; }
        for (let i = start; i < candidates.length; i++) {
            if (candidates[i] > remaining) break;
            if (i > start && candidates[i] === candidates[i - 1]) continue;
            path.push(candidates[i]);
            backtrack(i + 1, remaining - candidates[i]);
            path.pop();
        }
    }
    backtrack(0, target);
    return result;
}

const norm = (arr: number[][]): string =>
    JSON.stringify(arr.map(a => [...a].sort((x, y) => x - y)).sort((a, b) => JSON.stringify(a) < JSON.stringify(b) ? -1 : 1));

console.assert(norm(combinationSum2([10,1,2,7,6,1,5], 8)) === norm([[1,1,6],[1,2,5],[1,7],[2,6]]));
console.assert(norm(combinationSum2([2,5,2,1,2], 5)) === norm([[1,2,2],[5]]));
console.assert(combinationSum2([1,2], 10).length === 0);
console.assert(norm(combinationSum2([3,3], 3)) === norm([[3]]));
console.log("all tests pass");

func combinationSum2(candidates []int, target int) [][]int {
    sort.Ints(candidates)
    result := [][]int{}
    path := []int{}
    var backtrack func(start, remaining int)
    backtrack = func(start, remaining int) {
        if remaining == 0 {
            cp := make([]int, len(path))
            copy(cp, path)
            result = append(result, cp)
            return
        }
        for i := start; i < len(candidates); i++ {
            if candidates[i] > remaining { break }
            if i > start && candidates[i] == candidates[i-1] { continue }
            path = append(path, candidates[i])
            backtrack(i+1, remaining-candidates[i])
            path = path[:len(path)-1]
        }
    }
    backtrack(0, target)
    return result
}

Arrays, sorted for pruning and dedup

Subsets and Combinations, the choice set pattern for selecting groups while controlling duplicates.
Backtracking, the explore, undo, and prune pattern for building candidates.

40. Combination Sum II (Medium)

Problem

Try it yourself

Approach 1: Brute force, all subsets, filter by sum, dedup

Approach 2: Backtracking with start index (no skip)

Approach 3: Sort + skip same-level duplicates (canonical)

Summary

Test cases

Related data structures

Related concepts

Approach 2: Backtracking with `start` index (no skip)