LeetCode 40: Combination Sum II

Problem Restatement

We are given an array candidates and an integer target.

We need to return all unique combinations where the chosen numbers sum to target.

Each number in candidates may be used at most once.

The input may contain duplicate values, but the answer must not contain duplicate combinations. The result may be returned in any order. The constraints are 1 <= candidates.length <= 100, 1 <= candidates[i] <= 50, and 1 <= target <= 30.

Input and Output

Function shape:

def combinationSum2(candidates: list[int], target: int) -> list[list[int]]:
    ...

Examples

Example 1:

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

Valid combinations are:

[1, 1, 6]
[1, 2, 5]
[1, 7]
[2, 6]

Return:

[[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]

Example 2:

candidates = [2, 5, 2, 1, 2]
target = 5

Valid combinations are:

[1, 2, 2]
[5]

Return:

[[1, 2, 2], [5]]

First Thought: Backtracking Over All Choices

A direct idea is to try every subset.

For each element, we either use it or skip it.

When the current sum reaches target, we save the current path.

This works in principle, but duplicate values create duplicate answers.

For example:

candidates = [1, 1, 2]
target = 3

The first 1 plus 2 gives:

[1, 2]

The second 1 plus 2 also gives:

[1, 2]

These are the same combination, so we need a duplicate-skipping rule.

Key Insight

Sort the array first.

After sorting, equal values become adjacent.

Then during backtracking, if we are choosing among candidates at the same recursion level, we skip duplicate values after the first one.

The rule is:

if i > start and candidates[i] == candidates[i - 1]:
    continue

This means:

If this value is the same as the previous value, and both are choices for the same slot in the combination, skip the later one.

This avoids duplicate combinations.

But we still allow duplicates when they come from different recursion levels.

For example, [1, 1, 6] is valid when there are two 1s in the input. The second 1 is allowed after choosing the first one because it is used at a deeper level, not as a duplicate sibling choice.

Algorithm

Sort candidates.

Use backtracking with:

Recursive function:

backtrack(start, remain)

Inside it:

1. If remain == 0, copy path into ans.
2. Loop i from start to the end.
3. If i > start and candidates[i] == candidates[i - 1], skip it.
4. If candidates[i] > remain, break.
5. Choose candidates[i].
6. Recurse with i + 1, because each element may be used once.
7. Undo the choice.

The key difference from LeetCode 39 is this recursive call:

backtrack(i + 1, remain - candidates[i])

In LeetCode 39, we used i because candidates could be reused.

Here, we use i + 1 because each element can be used at most once.

Correctness

The algorithm only adds a path to the answer when remain == 0. Since remain starts as target and every chosen value is subtracted from it, this means the chosen values sum exactly to target.

No element is used more than once. After choosing index i, the recursive call starts at i + 1, so index i cannot be chosen again.

Every generated path follows increasing index order. Therefore, each subset of indices has only one possible generation order.

The duplicate-skipping rule removes repeated sibling choices. When two equal values appear next to each other, choosing the later one as the first choice at the same recursion level would create the same value combination as choosing the earlier one. Skipping it removes that duplicate branch.

The rule does not block valid repeated values in a combination. If we choose the first duplicate value, the next recursive level starts after it, where the second duplicate value may still be chosen.

Therefore, the algorithm returns every valid unique combination exactly once.

Complexity

Sorting costs O(n log n), which is dominated by the backtracking search in the worst case.

Implementation

class Solution:
    def combinationSum2(self, candidates: list[int], target: int) -> list[list[int]]:
        candidates.sort()

        ans = []
        path = []

        def backtrack(start: int, remain: int) -> None:
            if remain == 0:
                ans.append(path.copy())
                return

            for i in range(start, len(candidates)):
                if i > start and candidates[i] == candidates[i - 1]:
                    continue

                value = candidates[i]

                if value > remain:
                    break

                path.append(value)
                backtrack(i + 1, remain - value)
                path.pop()

        backtrack(0, target)
        return ans

Code Explanation

We sort first:

candidates.sort()

This makes duplicates adjacent and enables early stopping.

The answer stores complete combinations:

ans = []

The path stores the current partial combination:

path = []

The recursive function receives the first index still available:

def backtrack(start: int, remain: int) -> None:

When remain == 0, the path is complete.

if remain == 0:
    ans.append(path.copy())
    return

Loop through available candidates:

for i in range(start, len(candidates)):

Skip duplicate values at the same recursion level:

if i > start and candidates[i] == candidates[i - 1]:
    continue

If the value is larger than the remaining target, stop.

if value > remain:
    break

Choose the value:

path.append(value)

Move to i + 1, so this element cannot be reused.

backtrack(i + 1, remain - value)

Undo the choice:

path.pop()

Testing

def normalize(result: list[list[int]]) -> list[list[int]]:
    return sorted(sorted(row) for row in result)

def check(candidates: list[int], target: int, expected: list[list[int]]) -> None:
    actual = Solution().combinationSum2(candidates, target)
    assert normalize(actual) == normalize(expected), (candidates, target, actual, expected)

def run_tests():
    check(
        [10, 1, 2, 7, 6, 1, 5],
        8,
        [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]],
    )

    check(
        [2, 5, 2, 1, 2],
        5,
        [[1, 2, 2], [5]],
    )

    check([1, 1, 1, 1], 2, [[1, 1]])
    check([3, 4, 5], 2, [])
    check([1], 1, [[1]])
    check([1], 2, [])
    check([1, 2, 2, 2, 5], 5, [[1, 2, 2], [5]])

    print("all tests passed")

run_tests()

Test meaning: