# LeetCode 39: Combination Sum

## Problem Restatement

We are given an array of distinct integers `candidates` and an integer `target`.

We need to return all unique combinations of numbers from `candidates` whose sum equals `target`.

Each candidate number may be chosen unlimited times.

Two combinations are considered different only when the frequency of at least one chosen number is different. The result may be returned in any order. The test cases guarantee fewer than `150` valid combinations.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `candidates` and `target` |
| Output | A list of valid combinations |
| Candidate reuse | Each candidate can be used unlimited times |
| Candidate values | Distinct integers |
| Combination order | `[2,2,3]` and `[2,3,2]` count as the same combination |

Function shape:

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

## Examples

Example 1:

```python
candidates = [2, 3, 6, 7]
target = 7
```

Valid combinations:

```python
[2, 2, 3]
[7]
```

Return:

```python
[[2, 2, 3], [7]]
```

Example 2:

```python
candidates = [2, 3, 5]
target = 8
```

Valid combinations:

```python
[2, 2, 2, 2]
[2, 3, 3]
[3, 5]
```

Return:

```python
[[2, 2, 2, 2], [2, 3, 3], [3, 5]]
```

Example 3:

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

No combination can sum to `1`.

Return:

```python
[]
```

## First Thought: Try Every Possible List

A direct idea is to try building every possible list of numbers.

At each step, choose any candidate and add it to the current list.

Stop when the sum reaches or exceeds `target`.

This finds valid answers, but it creates duplicates.

For example, with:

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

we may generate both:

```python
[2, 3]
[3, 2]
```

These are the same combination because they use one `2` and one `3`.

We need a way to generate each frequency pattern only once.

## Key Insight

Force combinations to be built in non-decreasing candidate-index order.

At each recursive call, we pass a `start` index.

The next chosen candidate must come from:

```python
candidates[start:]
```

If we choose `candidates[i]`, the recursive call starts again at `i`, not `i + 1`, because the same number may be reused.

That gives us two important properties:

| Rule | Effect |
|---|---|
| Recurse with `i` | Allows unlimited reuse of the same candidate |
| Never go back to smaller indices | Prevents duplicate permutations |

For example, after choosing `3`, we never go back and choose `2`.

So `[3, 2]` is never generated if `[2, 3]` already represents that combination.

## Algorithm

Sort `candidates`.

Then use backtracking with:

| Variable | Meaning |
|---|---|
| `start` | First candidate index allowed in this call |
| `remain` | Remaining sum needed to reach `target` |
| `path` | Current partial combination |
| `ans` | All valid combinations found |

Recursive function:

```python
backtrack(start, remain)
```

Base cases:

1. If `remain == 0`, copy `path` into `ans`.
2. If `remain < 0`, stop.

For each index `i` from `start` to the end:

1. Let `value = candidates[i]`.
2. If `value > remain`, break because the array is sorted.
3. Append `value` to `path`.
4. Recurse with `backtrack(i, remain - value)`.
5. Pop `value` from `path`.

## Correctness

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

The algorithm never creates invalid combinations in the answer. If a path exceeds the target, then `remain` becomes negative or a sorted pruning condition stops that branch before it can be recorded.

Every valid combination can be represented in non-decreasing candidate-index order. The algorithm explores exactly that kind of order because each recursive call only allows candidates from the current index onward. Since choosing index `i` recurses with `i`, the same candidate can appear multiple times.

The algorithm also avoids duplicates. Any duplicate ordering such as `[3, 2]` would require going from a larger candidate index back to a smaller one. The `start` rule forbids that. Therefore, each unique frequency pattern is generated once.

So the algorithm returns all and only valid unique combinations.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | Exponential | The search may explore many partial combinations |
| Space | `O(target / min(candidates))` excluding output | This is the maximum recursion depth |

The output itself can contain many lists. The problem guarantees fewer than `150` valid combinations for the given input.

## Implementation

```python
class Solution:
    def combinationSum(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)):
                value = candidates[i]

                if value > remain:
                    break

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

        backtrack(0, target)
        return ans
```

## Code Explanation

Sort the candidates first:

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

Sorting lets us stop early when a candidate is already larger than the remaining sum.

The answer list stores complete combinations:

```python
ans = []
```

The `path` list stores the current partial combination:

```python
path = []
```

The recursive function receives the first candidate index still allowed:

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

When `remain == 0`, the current path is complete:

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

We must append a copy because `path` will keep changing during backtracking.

Now try each allowed candidate:

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

If the value is too large, all later values are also too large because the array is sorted:

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

Choose the value:

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

Recurse with `i`, not `i + 1`, because the same value may be chosen again:

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

Undo the choice before trying the next value:

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

Finally, start the search:

```python
backtrack(0, target)
```

## 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().combinationSum(candidates, target)
    assert normalize(actual) == normalize(expected), (candidates, target, actual, expected)

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

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[2,3,6,7]`, target `7` | Basic reuse case |
| `[2,3,5]`, target `8` | Multiple valid combinations |
| `[2]`, target `1` | No solution |
| `[1]`, target `2` | Reuse same candidate |
| Unsorted candidates | Confirms sorting works |
| All candidates too large | Returns empty list |