## 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:**

= [1, 2, 3]nums= 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 istarget.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?

**Credits:**

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

## Rust Solution

```
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);
}
```

Having problems with this solution? Click here to submit an issue on github.