| Category | Difficulty | Likes | Dislikes |
|---|
| algorithms | Medium (53.15%) | 751 | - |
Tags
dynamic-programming
Companies
facebook | google | snapchat
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
示例 1：
1
2
3
4
5
6
7
8
9
10
11
12
| 输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。
|
示例 2：
1
2
| 输入：nums = [9], target = 3
输出：0
|
提示：
1 <= nums.length <= 2001 <= nums[i] <= 1000nums 中的所有元素 互不相同1 <= target <= 1000
**进阶：**如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？
Discussion | Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| impl Solution {
/// ## 解题思路
/// ### 动态规划
/// - 设`dp[t]`表示`target == t`的组合总数；
/// - 则对于nums中的任何一个n, dp[t-n]表示target == t-n的组合总数；
/// 如果在该组合数组中增加一个n, 则target == t;
/// - 故: `dp[t] = sum(dp[t-n]), (n为nums中的所有数)`
/// - 初始条件: `dp[0] = 1`
/// - 终止条件: `dp[target]`
pub fn combination_sum4(nums: Vec<i32>, target: i32) -> i32 {
let mut dp = vec![0; target as usize + 1];
dp[0] = 1;
for t in 1..=target {
for &n in &nums {
if n <= t {
dp[t as usize] += dp[(t - n) as usize];
}
}
}
dp[target as usize]
}
}
// @lc code=end
struct Solution;
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test() {
assert_eq!(Solution::combination_sum4(vec![1, 2, 3], 4), 7);
}
}
|