# Combination Sum IV
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/combination-sum-iv)
Canonical: https://scaleengineer.com/dsa/problems/combination-sum-iv
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [Snap](https://scaleengineer.com/companies/snap)
---
## Problem
Given an array of **distinct** integers `nums` and a target integer `target`, return _the number of possible combinations that add up to_ `target`.

The test cases are generated so that the answer can fit in a **32-bit** integer.

**Example 1:**

**Input:** nums = [1,2,3], target = 4
**Output:** 7
**Explanation:**
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.

**Example 2:**

**Input:** nums = [9], target = 3
**Output:** 0

**Constraints:**

* `1 <= nums.length <= 200`
* `1 <= nums[i] <= 1000`
* All the elements of `nums` are **unique**.
* `1 <= target <= 1000`

**Follow up:** What if negative numbers are allowed in the given array? How does it change the problem? What limitation we need to add to the question to allow negative numbers?

# Approaches
## Brute-force Recursion
This approach uses a simple recursive function to explore all possible combinations of numbers from the `nums` array that can sum up to the `target`. It directly translates the problem's recurrence relation into code.
**Time:** O(N^T), where N is the number of elements in `nums` and T is the target value. In the worst-case scenario (e.g., `nums` contains 1), the recursion tree can have a depth of T and each node can branch N times. This leads to an exponential number of calls and will likely result in a 'Time Limit Exceeded' error for larger inputs. · **Space:** O(T), for the recursion stack depth. The maximum depth of the recursion is proportional to the target value T.
**Pros:** Simple to understand and implement.
**Cons:** Extremely inefficient due to re-computing the same subproblems multiple times.; Will not pass for larger test cases due to 'Time Limit Exceeded'.
### Explanation
We define a recursive function, let's call it `findCombinations(remainingTarget)`. The base cases for the recursion are: if `remainingTarget` is 0, it means we've found a valid combination, so we return 1. If `remainingTarget` is negative, it's an invalid path, so we return 0. For the recursive step, we iterate through each number `num` in the `nums` array. For each `num`, we make a recursive call with `findCombinations(remainingTarget - num)`. The total number of combinations for `remainingTarget` is the sum of the results from these recursive calls. This method explores every single possibility, leading to a large number of redundant calculations for the same subproblems (i.e., the same `remainingTarget` value).

```java
class Solution {
    public int combinationSum4(int[] nums, int target) {
        if (target == 0) {
            return 1;
        }
        if (target < 0) {
            return 0;
        }

        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            res += combinationSum4(nums, target - nums[i]);
        }
        return res;
    }
}
```
### Algorithm
1. Define a recursive function `combinationSum4(nums, target)`.
2. **Base Case 1:** If `target == 0`, it means a valid combination is found. Return 1.
3. **Base Case 2:** If `target < 0`, it's an invalid path. Return 0.
4. Initialize a counter `count = 0`.
5. Iterate through each number `num` in the `nums` array.
6. For each `num`, make a recursive call `combinationSum4(nums, target - num)` and add the result to `count`.
7. Return the total `count`.

## Top-Down Dynamic Programming with Memoization
This approach improves upon the brute-force recursion by using memoization to store the results of subproblems. By caching results, we avoid redundant computations for the same remaining target values.
**Time:** O(N * T), where N is the number of elements in `nums` and T is the target. Each state from 0 to T is computed only once. For each state, we iterate through the N numbers in `nums`. · **Space:** O(T), for the recursion stack depth and the memoization array of size `target + 1`.
**Pros:** Significantly more efficient than brute-force.; Guaranteed to pass within time limits for the given constraints.
**Cons:** Has the overhead of recursive function calls.; Can lead to a stack overflow error for very large targets, though not an issue with the given constraints.
### Explanation
This is a refinement of the recursive approach. We introduce a cache (e.g., an array or a map, often called a memoization table) to store the results for each `remainingTarget` that has already been computed. We use a memoization array, `memo`, of size `target + 1`, initialized with a value like -1 to indicate that a state has not been computed. The recursive function `findCombinations(remainingTarget, memo)` first checks if the result for `remainingTarget` is already in our memo table. If it is, we return the stored value immediately. If not, we compute it as in the brute-force approach, and before returning, we store the result in `memo[remainingTarget]`. This ensures that each subproblem is solved only once.

```java
import java.util.Arrays;

class Solution {
    private int[] memo;

    public int combinationSum4(int[] nums, int target) {
        memo = new int[target + 1];
        Arrays.fill(memo, -1);
        return solve(nums, target);
    }

    private int solve(int[] nums, int target) {
        if (target == 0) {
            return 1;
        }
        if (target < 0) {
            return 0;
        }
        if (memo[target] != -1) {
            return memo[target];
        }

        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            res += solve(nums, target - nums[i]);
        }

        memo[target] = res;
        return res;
    }
}
```
### Algorithm
1. Create a memoization array `memo` of size `target + 1` and fill it with a sentinel value (e.g., -1).
2. Define a helper function `solve(nums, target, memo)`.
3. **Base Case 1:** If `target == 0`, return 1.
4. **Base Case 2:** If `target < 0`, return 0.
5. **Memoization Check:** If `memo[target]` is not -1, it means the result is already computed. Return `memo[target]`.
6. Initialize a counter `count = 0`.
7. Iterate through each `num` in `nums`.
8. Add the result of `solve(nums, target - num, memo)` to `count`.
9. Store the result in the memoization table: `memo[target] = count`.
10. Return `count`.

## Bottom-Up Dynamic Programming (Tabulation)
This is an iterative approach that builds the solution from the bottom up. It uses an array to store the number of combinations for all sums from 0 to the target, calculating each value based on previously computed smaller values.
**Time:** O(N * T), where N is the number of elements in `nums` and T is the target. This is due to the two nested loops. · **Space:** O(T), for the DP array of size `target + 1`.
**Pros:** Most efficient approach in terms of constant factors as it avoids recursion overhead.; No risk of stack overflow.; Often considered more intuitive for DP problems.
**Cons:** Slightly less direct translation of the recurrence relation compared to the top-down approach.
### Explanation
We create a DP array, `dp`, of size `target + 1`. `dp[i]` will store the number of ways to form the sum `i`. The base case is `dp[0] = 1`, as there is one way to make a sum of 0 (by choosing no numbers). We then iterate from `i = 1` to `target`. For each `i`, we calculate `dp[i]`. The value of `dp[i]` is the sum of `dp[i - num]` for every `num` in `nums` where `i >= num`. This is because if we can form a sum `i - num`, we can add `num` to it to form the sum `i`. This is implemented using two nested loops. The outer loop iterates through the targets from 1 to `target`, and the inner loop iterates through the numbers in `nums`. The final answer is stored in `dp[target]`.

```java
class Solution {
    public int combinationSum4(int[] nums, int target) {
        // dp[i] will store the number of combinations that sum up to i.
        int[] dp = new int[target + 1];

        // There is one way to make sum 0, which is by choosing no elements.
        dp[0] = 1;

        // Iterate from 1 to target to fill the dp array.
        for (int i = 1; i <= target; i++) {
            // For each target sum i, iterate through the numbers.
            for (int num : nums) {
                // If we can form sum i by using num, add the number of ways.
                if (i - num >= 0) {
                    // Check for potential overflow before adding, though problem statement says it fits in int.
                    if (dp[i] > Integer.MAX_VALUE - dp[i - num]) {
                        // This case might not be hit due to problem constraints but is good practice.
                    } else {
                        dp[i] += dp[i - num];
                    }
                }
            }
        }

        return dp[target];
    }
}
```

### Follow-up Discussion: Negative Numbers
If negative numbers were allowed in `nums`, the problem changes significantly. The current DP approach relies on building solutions for larger targets from smaller ones (`dp[i]` depends on `dp[i-num]`). If `num` is negative, `i-num` would be greater than `i`, breaking the bottom-up structure.

More critically, if there's a combination of numbers that sums to zero (e.g., `[1, -1]`), or even just a single negative number, you could create an infinite number of combinations for a given target (e.g., for target `t`, you can use `(t)`, `(t, 1, -1)`, `(t, 1, -1, 1, -1)`, etc.).

To make the problem solvable with negative numbers, we would need an additional constraint, such as limiting the maximum number of elements in a combination. Without such a constraint, the number of combinations could be infinite.
### Algorithm
1. Create a DP array `dp` of size `target + 1` and initialize all elements to 0.
2. Set the base case: `dp[0] = 1`.
3. Iterate `i` from 1 to `target` (this represents the current sum we are trying to achieve).
4. Inside this loop, iterate through each `num` in the `nums` array.
5. If the current sum `i` is greater than or equal to `num`, it means we can form `i` by adding `num` to a combination that sums to `i - num`. So, we update `dp[i]` by adding `dp[i - num]` to it.
6. After the loops complete, `dp[target]` will hold the total number of combinations. Return `dp[target]`.

# Solutions
### CSharp

```csharp
public class Solution { public int CombinationSum4 ( int [] nums , int target ) { int [] f = new int [ target + 1 ]; f [ 0 ] = 1 ; for ( int i = 1 ; i <= target ; ++ i ) { foreach ( int x in nums ) { if ( i >= x ) { f [ i ] += f [ i - x ]; } } } return f [ target ]; } }
```

### Java

```java
public class Combination_Sum_IV { class Solution { public int combinationSum4 ( int [] nums , int target ) { // dp[i] meaning for value i, how many combination count int [] dp = new int [ target + 1 ]; dp [ 0 ] = 1 ; for ( int targetValue = 1 ; targetValue <= target ; targetValue ++) { for ( int i = 0 ; i < nums . length ; i ++) { if ( nums [ i ] <= targetValue ) { // @note: not dp[targetValue]=dp[targetValue-a]+dp[a] // becasue both will be added in below line for dp[a] and dp[targetValue-a] dp [ targetValue ] += dp [ targetValue - nums [ i ]]; } } } return dp [ target ]; } } } ////// class Solution { public int combinationSum4 ( int [] nums , int target ) { int [] dp = new int [ target + 1 ]; dp [ 0 ] = 1 ; for ( int i = 1 ; i <= target ; ++ i ) { for ( int num : nums ) { if ( i >= num ) { dp [ i ] += dp [ i - num ]; } } } return dp [ target ]; } }
```

### JavaScript

```javascript
/** * @param {number[]} nums * @param {number} target * @return {number} */ var combinationSum4 =
  function (nums, target) {
    const f = new Array(target + 1).fill(0);
    f[0] = 1;
    for (let i = 1; i <= target; ++i) {
      for (const x of nums) {
        if (i >= x) {
          f[i] += f[i - x];
        }
      }
    }
    return f[target];
  };

```

### CPP

```cpp
class Solution {
public:
  int combinationSum4(vector<int> &nums, int target) {
    int f[target + 1];
    memset(f, 0, sizeof(f));
    f[0] = 1;
    for (int i = 1; i <= target; ++i) {
      for (int x : nums) {
        if (i >= x && f[i - x] < INT_MAX - f[i]) {
          f[i] += f[i - x];
        }
      }
    }
    return f[target];
  }
};

```

### Python

```python
class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int: f = [1] + [0] * target for i in range(1, target + 1): for x in nums: if i >= x: f[i] += f[i - x] return f[target]

```