leetcode/
combination_sum_4.rs

1//! # 377. 组合总和 Ⅳ
2//!
3//! 难度 中等
4//!
5//! 给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。
6//!
7//! ## 示例:
8//!
9//! ```text
10//! nums = [1, 2, 3]
11//! target = 4
12//!
13//! 所有可能的组合为：
14//! (1, 1, 1, 1)
15//! (1, 1, 2)
16//! (1, 2, 1)
17//! (1, 3)
18//! (2, 1, 1)
19//! (2, 2)
20//! (3, 1)
21//!
22//! 请注意，顺序不同的序列被视作不同的组合。
23//!
24//! 因此输出为 7。
25//! ```
26//!
27//! ## 进阶：
28//!
29//! - 如果给定的数组中含有负数会怎么样？
30//! - 问题会产生什么变化？
31//! - 我们需要在题目中添加什么限制来允许负数的出现？
32//!
33//! See [leetcode](https://leetcode-cn.com/problems/combination-sum-iv/)
34
35pub struct Solution;
36
37impl Solution {
38    pub fn combination_sum4(nums: Vec<i32>, target: i32) -> i32 {
39        debug_assert!(target >= 0);
40
41        let mut s = Vec::with_capacity(target as usize + 1);
42        s.push(1);                                           // 空集 1 个
43
44        for i in 1..=target as usize {
45            s.push(0);                                       // init s[i]
46            for &n in nums.iter() {
47                if n as usize <= i {
48                    s[i] += s[i - n as usize];
49                }
50            }
51        }
52        s[target as usize]
53    }
54}
55
56#[cfg(test)]
57mod tests {
58    use super::Solution;
59
60    #[test]
61    fn test() {
62        let t = |nums, t| Solution::combination_sum4(nums, t);
63        assert_eq!(7, t(vec![1,2,3], 4));
64    }
65}
leetcode/combination_sum_4.rs

leetcode/
combination_sum_4.rs
