# Question

Formatted question description: https://leetcode.ca/all/377.html

/**
377. Combination Sum IV

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?

*/



# Algorithm

One-dimensional array dp, where dp[i] represents the number of solutions whose target number is i, and then traverses from 1 to target.

For each number i, traverse the nums array, if i>=x

int[] dp = new int[target + 1];

If there is negative numbers allowed, there could be infinite possibilities.

• e.g. target = 1, there is [-1, 1] in nums, then the possible ways could be -1+1+1, -1-1+1+1+1

If allowing negative numbers, there can’t be any combiantion of neigatie numers + any combiantion of positive numbers == 0.

# Code

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 = 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];
}
}

}

• // OJ: https://leetcode.com/problems/combination-sum-iv/
// Time: O(NT)
// Space: O(T)
class Solution {
unordered_map<int, int> m { {0, 1} };
int dp(vector<int>& nums, int target) {
if (m.count(target)) return m[target];
int cnt = 0;
for (int n : nums) {
if (n > target) break;
cnt += dp(nums, target - n);
}
return m[target] = cnt;
}
public:
int combinationSum4(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
return dp(nums, target);
}
};

• class Solution(object):
def combinationSum4(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
dp =  * (target + 1)
dp = 1

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