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?

Credits:
Special thanks to @pbrother for adding this problem and creating all test cases.

377. Combination Sum IV
``````struct Solution;

impl Solution {
fn combination_sum4(nums: Vec<i32>, target: i32) -> i32 {
let k = target as usize;
let mut dp = vec![0; k + 1];
dp[0] = 1;
for i in 1..=target {
for &j in &nums {
if i - j >= 0 {
dp[i as usize] += dp[(i - j) as usize];
}
}
}
dp[k]
}
}

#[test]
fn test() {
let nums = vec![1, 2, 3];
let target = 4;
let res = 7;
assert_eq!(Solution::combination_sum4(nums, target), res);
}
``````