# LeetCode 377: Combination Sum IV

## Problem Restatement

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

We need to count how many possible ordered combinations can add up to `target`.

Each number in `nums` can be used multiple times.

Order matters.

That means these are counted as different combinations:

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

Even though they use the same numbers, their order is different.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An array `nums` and an integer `target` |
| Output | Number of ordered combinations that sum to `target` |
| Constraint | `1 <= nums.length <= 200` |
| Constraint | `1 <= nums[i] <= 1000` |
| Constraint | All elements in `nums` are unique |
| Constraint | `1 <= target <= 1000` |
| Guarantee | The answer fits in a 32-bit integer |

Example function shape:

```python
def combinationSum4(nums: list[int], target: int) -> int:
    ...
```

## Examples

Example 1:

```python
nums = [1, 2, 3]
target = 4
```

The possible ordered combinations are:

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

There are `7` combinations.

So the answer is:

```python
7
```

Example 2:

```python
nums = [9]
target = 3
```

The only number is `9`, which is already larger than `3`.

There is no way to form `3`.

So the answer is:

```python
0
```

## First Thought: Backtracking

A direct approach is to try every possible sequence.

At each step, choose one number from `nums`, subtract it from the remaining target, and continue.

If the remaining target becomes `0`, we found one valid sequence.

If it becomes negative, that path fails.

Example:

```python
nums = [1, 2, 3]
target = 4
```

From `4`, we may choose `1`, `2`, or `3`.

If we choose `1`, the remaining target is `3`.

From `3`, we again may choose `1`, `2`, or `3`.

This creates a large recursion tree.

Code shape:

```python
class Solution:
    def combinationSum4(self, nums: list[int], target: int) -> int:
        def dfs(remain: int) -> int:
            if remain == 0:
                return 1

            if remain < 0:
                return 0

            total = 0
            for num in nums:
                total += dfs(remain - num)

            return total

        return dfs(target)
```

This is correct, but it recomputes the same remaining targets many times.

For example, `dfs(2)` may be reached from several different sequences.

## Problem With Brute Force

The brute force recursion branches by every number in `nums`.

Many paths share the same remaining target.

For example, with:

```python
nums = [1, 2, 3]
target = 4
```

The remaining target `2` can appear after:

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

Both paths ask the same question:

“How many ordered combinations form sum `2`?”

This repeated work suggests dynamic programming.

## Key Insight

Let:

```python
dp[s]
```

mean:

```text
the number of ordered combinations that sum to s
```

We want:

```python
dp[target]
```

The base case is:

```python
dp[0] = 1
```

There is exactly one way to form sum `0`: choose nothing.

Now consider a target sum `s`.

To build a sequence that sums to `s`, choose the last number in the sequence.

If the last number is `num`, then the previous part must sum to:

```python
s - num
```

So every combination counted in `dp[s - num]` can become a combination for `s` by appending `num`.

Therefore:

```python
dp[s] += dp[s - num]
```

for every `num` where `s >= num`.

## Algorithm

Create an array:

```python
dp = [0] * (target + 1)
```

Set:

```python
dp[0] = 1
```

Then compute answers for all sums from `1` to `target`.

For each sum `s`:

1. Try every number `num` in `nums`.
2. If `num <= s`, add `dp[s - num]` into `dp[s]`.
3. After filling the table, return `dp[target]`.

The loop order matters.

We loop over sums first, then numbers:

```python
for s in range(1, target + 1):
    for num in nums:
        ...
```

This counts ordered combinations.

For example, `[1, 3]` and `[3, 1]` are counted separately because they are formed through different last-number choices.

## Correctness

We prove that `dp[s]` stores the number of ordered combinations that sum to `s`.

The base case is `dp[0] = 1`. This represents the empty sequence. It is needed so that when `s == num`, the sequence `[num]` contributes one valid way.

Now assume all values smaller than `s` are correct.

For sum `s`, every valid ordered combination has a last number. Suppose that last number is `num`.

Then the part before the last number must sum to `s - num`.

By the assumption, there are exactly `dp[s - num]` ordered combinations for that previous sum.

Appending `num` to each of those combinations gives valid ordered combinations for `s`.

Also, every valid ordered combination for `s` appears in exactly one group, determined by its last number. So the groups do not overlap.

Therefore summing `dp[s - num]` over all usable `num` gives exactly the number of ordered combinations for `s`.

By induction, `dp[target]` is correct.

## Complexity

Let `n = len(nums)`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(target * n)` | For each sum, we try every number |
| Space | `O(target)` | We store one DP value for each sum from `0` to `target` |

## Implementation

```python
class Solution:
    def combinationSum4(self, nums: list[int], target: int) -> int:
        dp = [0] * (target + 1)
        dp[0] = 1

        for s in range(1, target + 1):
            for num in nums:
                if num <= s:
                    dp[s] += dp[s - num]

        return dp[target]
```

## Code Explanation

We create a DP table:

```python
dp = [0] * (target + 1)
```

`dp[s]` means the number of ordered combinations that sum to `s`.

The base case is:

```python
dp[0] = 1
```

This means there is one way to form sum `0`: use no numbers.

Then we fill the table from smaller sums to larger sums:

```python
for s in range(1, target + 1):
```

For each sum, we try every possible last number:

```python
for num in nums:
```

If `num` can fit inside the current sum:

```python
if num <= s:
```

then every way to form `s - num` can be extended by appending `num`:

```python
dp[s] += dp[s - num]
```

Finally, the answer is:

```python
return dp[target]
```

## Testing

```python
def test_solution():
    s = Solution()

    assert s.combinationSum4([1, 2, 3], 4) == 7
    assert s.combinationSum4([9], 3) == 0
    assert s.combinationSum4([1], 5) == 1
    assert s.combinationSum4([2], 3) == 0
    assert s.combinationSum4([2, 4, 6], 8) == 7
    assert s.combinationSum4([3, 4, 5], 2) == 0

    print("all tests passed")

test_solution()
```

Test meaning:

| Test | Why |
|---|---|
| `[1, 2, 3]`, target `4` | Main example where order matters |
| `[9]`, target `3` | Number larger than target |
| `[1]`, target `5` | Only one repeated choice |
| `[2]`, target `3` | Cannot form odd target |
| `[2, 4, 6]`, target `8` | Multiple ordered combinations with even numbers |
| `[3, 4, 5]`, target `2` | All numbers larger than target |