LeetCode 377——组合总和 Ⅳ

1. 题目

2. 解题思路

此题一看应该就是需要用到动态规划算法，假设我们以 f[d]表示总和为 d 的元素组合的个数，首先，我们遍历 nums 数组，

如果有 nums[i] < target，那么组合中第一个元素我们放置 nums[i]，组合中余下元素的排列总个数也就变成了子问题 f[target - nums[i]]。

如果有 nums[i] = target，那么组合中只能放置 nums[i]这一个元素。

3. 代码实现

于是，我开始实现了第一版代码，完全就照着上面的解题思路来写，使用递归。

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {int ret = 0;for (int i = 0; i < nums.size(); ++i) {if (nums[i] < target) {ret += combinationSum4(nums, target-nums[i]);}else if (nums[i] == target) {ret += 1;}}return ret;}
};

很可惜，没有通过全部测试用例，超时了。

超出时间限制 10 / 16 个通过的测试用例

这里，计算 f[target - nums[i]]的时候有可能存在大量重复，比如，nums=[1, 2, 3, 4], target=5，第一个元素我们放置 2 时，需要计算 f(3)。然后，如果前两个元素我们都放置 1 时，也需要计算 f(3)。

所以，一个很自然的思路就是把已经计算过的 f(d)记录下来，下次遇到可以直接用。

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {static vector<int> target_ret(1001, -1);int ret = 0;for (int i = 0; i < nums.size(); ++i) {if (nums[i] < target) {int left = target - nums[i];if (target_ret[left] == -1) {target_ret[left] = combinationSum4(nums, left); }ret += target_ret[left];}else if (nums[i] == target) {ret += 1;}}return ret;}
};

于是，我定义了一个静态数组，全部初始化为 -1，计算一个 f(d) 后就把它记录下来，下次直接使用，不用再递归去调用一次函数。

但是，这次直接变成解答错误了。我把错误的用例单独拿出来测试，答案是对的。去网上一查，原来 LeetCode 会用这同一个类去测试所有的测试用例，那么我的静态数组就会受到前一个测试用例的影响，所以，答案也就是错的了，此路看来也不通！

那就只能手动递推了，因为我们最终要计算 f(target) ，而 f(target) 可能依赖于 f(target-1)、f(target-2)....f(1)，所以我们就从 1 开始，一个一个往后计算 f(d) 即可。

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<int> target_ret(target+1, 0);for (int j = 1; j <= target; ++j) {for (int i = 0; i < nums.size(); ++i) {if (nums[i] < j) {int left = j - nums[i];target_ret[j] += target_ret[left];}else if (nums[i] == j) {target_ret[j] += 1;}}}return target_ret[target];}
};

很不幸，还是出错了，看起来是整型数超出表示范围了，一个简单的思路是把 int 换成 unsigned int，终于成功了！

Line 16: Char 35: runtime error: signed integer overflow: 2147483647 + 1 cannot be represented in type ‘int’ (solution.cpp)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:25:35

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<unsigned int> target_ret(target+1, 0);for (int j = 1; j <= target; ++j) {for (int i = 0; i < nums.size(); ++i) {if (nums[i] < j) {int left = j - nums[i];target_ret[j] += target_ret[left];}else if (nums[i] == j) {target_ret[j] += 1;}}}return target_ret[target];}
};

要细究为什么会越界的话，其实题目描述里特别说明了 ：

题目数据保证答案符合 32 位整数范围。

但是这里只是说 f(target) 不会越界，我们从 1 遍历到 target 的某个中间变量可能越界了，然后这个中间变量实际上是用不到的。

比如，nums=[2, 6, 9], target=15， f(14) 是不会用到的，但是我们也会计算它。

时间复杂度为 $O(target\ast nums.size())$，空间复杂度为 $O(target)$。

如果数组中存在负数的话，会存在一个包含正数和负数的序列，它们的和为 0，也就是说，可以无限添加这个序列，而和保持不变，这样，f(target) 就是无穷的了。