# 377. Combination Sum IV 组合总和 Ⅳ

@TOC

## # 题目描述

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.
``````

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

## # 解题方法

0+4 1 （1+1+1+1） 1+3 1的组合3的组合 2+2 2的组合2的组合 3+1 3的组合*1的组合 4+0 1 （4）

1+4+4+4+1 然后除以2 因为重复了一遍 但是结果似乎不对

dp[n] = dp[n] + dp[n-i] 比如4 从1遍历到4 1<4 dp[4] = dp[4] + dp[4-1]

Python解法如下：

``````class Solution(object):
def combinationSum4(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
dp = [0] * (target + 1)
dp[0] = 1
for i in xrange(1, target + 1):
for num in nums:
if i >= num:
dp[i] += dp[i - num]
return dp.pop()
``````

C++代码如下：

``````class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<int> dp(target + 1, 0);
dp[0] = 1;
for (int i = 1; i <= target; i++) {
for (auto a : nums) {
if (i >= a) {
dp[i] += dp[i - a];
}
}
}
return dp.back();
}
};
``````

## # 日期

2018 年 2 月 21 日 2018 年 12 月 20 日 —— 感冒害的我睡不着