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