LeetCode 377——组合总和 Ⅳ

阅读目录

- 1. 题目
- 2. 解题思路
- 3. 代码实现

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];
    }
};