Halo

A magic place for coding

0%

LeetCode 解题报告(350) -- 377. Combination Sum IV

Problem

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

The answer is guaranteed to fit in a 32-bit integer.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
Input: nums = [1,2,3], target = 4
Output: 7
Explanation:
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.

Example 2:

1
2
Input: nums = [9], target = 3
Output: 0

Constraints:

  • 1 <= nums.length <= 200
  • 1 <= nums [i] <= 1000
  • All the elements of nums are unique.
  • 1 <= target <= 1000

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?


Analysis

   题目给出一个数组,还有一个 target 值,通过在数组中选取数字,使得这些数字的和等于 target,问这样的组合有多少个?其中数组中的数字是可以重复使用的。这种类型的题目暴力解法大概率都会超时的,所以就要想一个优化的方法。

   题目特意说到不同的排列也算不同,就是说 [1,1,2][2, 1, 1] 达到的效果是相同的,但是算两种。这类型题目主流的优化思路都是记录中间就算状态,也就是 dp 了。因为求目标值,所以直接定义 dp [i] 为和为 i 的排列数量。这样定义的好处是,无论怎么排列,都会在前面都计算好,比如说给出的数组是 [1, 2, 3],和为 3 的排列 dp [3] 就包括了 [1,1,1][1,2][2,1][3] 这些情况,当我们计算 dp [4] 的时候,就可以直接利用 dp [3] 来计算了。


Solution

   根据上面的思路,我们需要构建的是 [1,target] 的 dp 值。每一个都需要遍历给出的数组,然后通过 i - num 找到在前面计算过的 dp 值加上。


Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<unsigned int> dp(target+1, 0);
dp [0] = 1;
for (int i = 1; i <= target; i++) {
for (auto &num: nums) {
if (i - num >= 0) {
dp [i] += dp [i - num];
}
}
}
return dp [target];
}
};

Summary

   这道题目是一道比较典型的 dp 题目,这道题目其实 dp 的痕迹很明显,但是计算会需要一点技巧。实际上我们只需要从小到大计算 dp 值即可,每次都遍历数组中的元素。这道题目的分享到这里,感谢你的支持!

Welcome to my other publishing channels