> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/leetcode/dynamic-programming/knapsack-problem/377-combination-sum-iv.md).

# 377    Combination Sum IV

## 377. [Combination Sum IV](https://leetcode.com/problems/combination-sum-iv/description/)

## 1. Question

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

**Example:**

```
nums = [1, 2, 3]

target = 4

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.

Therefore the output is 7.
```

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

## 2. Implementation

**(1) DP**

思路: 每个nums的元素都可以不停地被用，很明显的完全背包类问题，按照模板写就好了。至于follow-up，如果允许负数的话，我们无法确定最后有多少种combination得到target. 如果要加条件使得我们在有负数的情况下得到target的话，**我觉得应该是每个数只能用一次**。

```java
class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;

        for (int j = 0; j <= target; j++) {
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] <= j) {
                    dp[j] += dp[j - nums[i]];
                }
            }
        }
        return dp[target];
    }
}
```

## 3. Time & Space Complexity

时间复杂度O(n \* target), 空间复杂度O(target)