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.

 

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.