# 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

| Item | Meaning |
|---|---|
| Input | `candidates` and `target` |
| Output | A list of unique combinations |
| Candidate reuse | Each element can be used once |
| Duplicate values | May exist in `candidates` |
| Duplicate answers | Must not appear |

Function shape:

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

## Examples

Example 1:

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

Valid combinations are:

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

Return:

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

Example 2:

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

Valid combinations are:

```python
[1, 2, 2]
[5]
```

Return:

```python
[[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:

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

The first `1` plus `2` gives:

```python
[1, 2]
```

The second `1` plus `2` also gives:

```python
[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:

```python
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 `1`s 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:

| Variable | Meaning |
|---|---|
| `start` | First index that can still be used |
| `remain` | Remaining sum needed |
| `path` | Current partial combination |
| `ans` | Final list of combinations |

Recursive function:

```python
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:

```python
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(2^n * n)` | In the worst case, we explore many subsets and copy paths |
| Space | `O(n)` excluding output | Recursion depth and current path can grow to `n` |

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

## Implementation

```python
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:

```python
candidates.sort()
```

This makes duplicates adjacent and enables early stopping.

The answer stores complete combinations:

```python
ans = []
```

The path stores the current partial combination:

```python
path = []
```

The recursive function receives the first index still available:

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

When `remain == 0`, the path is complete.

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

Loop through available candidates:

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

Skip duplicate values at the same recursion level:

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

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

```python
if value > remain:
    break
```

Choose the value:

```python
path.append(value)
```

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

```python
backtrack(i + 1, remain - value)
```

Undo the choice:

```python
path.pop()
```

## Testing

```python
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:

| Test | Why |
|---|---|
| `[10,1,2,7,6,1,5]`, target `8` | Standard mixed example |
| `[2,5,2,1,2]`, target `5` | Duplicate-heavy example |
| `[1,1,1,1]`, target `2` | Many duplicate values, one unique answer |
| `[3,4,5]`, target `2` | No candidate can be used |
| `[1]`, target `1` | Single element success |
| `[1]`, target `2` | Single element failure |
| `[1,2,2,2,5]`, target `5` | Duplicate skipping with repeated valid value |