# LC 377. Combination Sum IV

### [Problem link](https://leetcode.com/problems/combination-sum-iv/)

###### tags: `leedcode` `python` `c++` `medium` `DP`

Given an array of **distinct** integers <code>nums</code> and a target integer <code>target</code>, return the number of possible combinations that add up to<code>target</code>.

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:**

- <code>1 <= nums.length <= 200</code>
- <code>1 <= nums[i] <= 1000</code>
- All the elements of <code>nums</code> are **unique** .
- <code>1 <= target <= 1000</code>

**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?

## Solution 1 - DP
#### Python

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

        for i in range(1, target + 1):
            for j in range(len(nums)):
                if i >= nums[j]:
                    dp[i] += dp[i - nums[j]]

        return dp[-1]

#### C++

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1, 0);
        dp[0] = 1;

        for (int i = 0; i <= target; i++) {
            for (int j = 0; j < nums.size(); j++) {
                // avoid dp[i] + dp[i - nums[j]] > INT_MAX
                if (i - nums[j] >= 0 && dp[i] < INT_MAX - dp[i - nums[j]]) {
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        return dp.back();
    }
};

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        int n = nums.size();

        vector<int> cache(target + 1, -1);
        function<int(int)> dfs = [&](int i) {
            if (i <= 0) {
                return 1;
            }
            if (cache[i] != -1) {
                return cache[i];
            }
            cache[i] = 0;
            for (int& num: nums) {
                if (num <= i) {
                    cache[i] += dfs(i - num);
                }
            }
            return cache[i];
        };
        return dfs(target);
    }
};

>### Complexity
>n = target
>m = nums.length
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(mn) | O(n) |

## Note
sol1:
遍歷從target開始, 再來是背包(nums)

ex: nums = [1, 2, 3], target = 4
i = 0, dp = 1, 0, 0, 0, 0
i = 1, dp = 1, 1, 0, 0, 0
i = 2, dp = 1, 1, 2, 0, 0
i = 3, dp = 1, 1, 2, 0, 0
i = 4, dp = 1, 1, 2, 4, 0
i = 5, dp = 1, 1, 2, 4, 7