# Question

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

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?

# 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

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

}

############

class Solution {
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for (int i = 1; i <= target; ++i) {
for (int num : nums) {
if (i >= num) {
dp[i] += dp[i - num];
}
}
}
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:
def combinationSum4(self, nums: List[int], target: int) -> int:
dp = [0] * (target + 1)
dp[0] = 1
for i in range(1, target + 1):
for num in nums:
if i >= num:
dp[i] += dp[i - num]
return dp[-1]
# no dup, because e.g for [1, 2, 3], when reaching 1, dp[target - 1] will be dp[ a-larger-number ] which will be 0,
# only until reaching to a larger number in nums[] then target-i will be a smaller number with populated counting

############

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 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]


• func combinationSum4(nums []int, target int) int {
dp := make([]int, target+1)
dp[0] = 1
for i := 1; i <= target; i++ {
for _, num := range nums {
if i >= num {
dp[i] += dp[i-num]
}
}
}
return dp[target]
}

• /**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var combinationSum4 = function (nums, target) {
const dp = new Array(target + 1).fill(0);
dp[0] = 1;
for (let i = 1; i <= target; ++i) {
for (let v of nums) {
if (i >= v) {
dp[i] += dp[i - v];
}
}
}
return dp[target];
};


• function combinationSum4(nums: number[], target: number): number {
const f: number[] = new Array(target + 1).fill(0);
f[0] = 1;
for (let i = 1; i <= target; ++i) {
for (const x of nums) {
if (i >= x) {
f[i] += f[i - x];
}
}
}
return f[target];
}


• public class Solution {
public int CombinationSum4(int[] nums, int target) {
int[] f = new int[target + 1];
f[0] = 1;
for (int i = 1; i <= target; ++i) {
foreach (int x in nums) {
if (i >= x) {
f[i] += f[i - x];
}
}
}
return f[target];
}
}