> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/4.depth-first-search/377.-combination-sum-iv.md).

# 377. Combination Sum IV

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?

### Solution:

**Version 1: DP**

backPack VI 和combination sum IV是同一题 本质上是背包问题，但是和BP IV又不一样，因为同一组数可以组成不同的组合 比如[1, 1, 2](https://www.jiuzhang.com/problem/combination-sum-iv/)和[1, 2, 1](https://www.jiuzhang.com/problem/combination-sum-iv/)在本题是两个解，所以j循环要放在外面，使得相同的一组数 有可能出现在不同的结果中

**典型的完全背包问题(**[518. Coin Change 2](https://leetcode.com/problems/coin-change-2/)**)。 如果 数相同 顺序不同 被认为是 不同 的答案，那么就先循环背包容量，再循环物品。 如果 数相同 顺序不同 被认为是 相同 的答案，那么就先循环物品，再循环背包容量。**

所以只要把(BP IV)中j循环翻出来即可： BP IV: for num in nums: for j in range(num, target + 1): dp[j](https://www.jiuzhang.com/problem/combination-sum-iv/) += dp[j - num](https://www.jiuzhang.com/problem/combination-sum-iv/)

BP VI: for j in range(1, target + 1): for num in nums: if num > j: continue dp[j](https://www.jiuzhang.com/problem/combination-sum-iv/) += dp[j - num](https://www.jiuzhang.com/problem/combination-sum-iv/)

```
class Solution {
    public int combinationSum4(int[] nums, int target) {
        
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length;
        int[][] dp = new int[target+1][n+1];
        //dp[0][...] = 0;
        // dp[..][0] = 1;
        
        for(int i = 0; i<=n; i++)
        {
            dp[0][i] = 1;
        }
        
        for(int i = 1; i<= target; i++)
        {
            for(int j = 1; j<= n; j++)
            {
                if(i- nums[j-1] >=0)
                {
                    // 注意这里最后是dp[i- nums[j-1]][n]
                    dp[i][j] = dp[i][j-1] + dp[i- nums[j-1]][n];
                }
                else
                {
                    dp[i][j] = dp[i][j-1];
                }
                
            }
        }
          return dp[target][n]; 
         
    }
}
```

**Version 2: Top down dfs+ memorization search (similar as other combination sum)**

```
class Solution {

    public int combinationSum4(int[] nums, int target) {
        int result = 0;
        Arrays.sort(nums);
        Map<Integer, Integer> memo = new HashMap<Integer, Integer>();
        result = dfs(target, nums, 0, memo);
        return result;
    }
    
    public int dfs(int count, int[] nums, int startIndex, Map<Integer, Integer> memo)
    {
        if(memo.containsKey(count))
        {
            return memo.get(count);
        }
        
        if(count == 0)
        {
            return 1;
        }
        
        if(count < 0)
        {
            return 0;
        }
        
        if(startIndex == nums.length)
        {
            return 0;
        }
        
        int result = 0;
        for(int i = startIndex; i< nums.length; i++)
        {
            if(nums[i] > count) continue;
            result += dfs(count-nums[i], nums, startIndex, memo);
        }
        
        memo.put(count, result);
        return result;
    }
}
```