每天一道LeetCode-----找到给定序列中所有和为某个值的集合或集合个数，序列中可以有/无重复项，集合元素顺序不同算不同集合等

Combination Sum

原题链接Combination Sum

给定一个无重复项的序列，找到所有和是target的集合，每个元素可以使用多次。

可以用深度优先（dfs），对于某个元素都有两种选择，一种是选择当前元素至少一次，一种是不选择当前元素，所以在查找集合时要分开处理。比如说，当前元素下标为1，那么

1. 选择该元素，然后仍然从位置1开始继续进行（这保证了下次的元素下标仍然是1，还可以决定选或不选，即至少选择一次）
2. 不选择该元素，从位置2开始继续进行

这两种情况都可以用一个循环来做，从当前位置开始遍历给定序列，对于每个元素，如果选择了那么就是情况1，如果没有选择就是情况2

代码如下

class Solution {
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {/* 按递增排序，递归时可以根据当前要选择的元素和target大小决定是否还需要继续 */std::sort(candidates.begin(), candidates.end());/* 结果 */vector<vector<int>> res;/* 当前找到的集合 */vector<int> cur;dfs(candidates, target, 0, cur, res);return res;}
private:/* 深度优先查找所有满足条件的集合，target代表和要求总和的差，为0表示找到一个集合 */void dfs(vector<int>& candidates, int target, int idx, vector<int>& cur, vector<vector<int>>& res){/* 找到一个集合，添加到结果集中 */if(target == 0){res.emplace_back(cur);}/* 如果当前位置越界或者当前元素大于所要求的数值，返回，因为是递增排序，后面的元素肯定也大于 */if(idx >= candidates.size() || candidates[idx] > target)return;for(int i = idx; i < candidates.size(); ++i){cur.emplace_back(candidates[i]);dfs(candidates, target - candidates[i], i, cur, res);cur.pop_back();}}
};

当然，如果觉得最后一个for循环不容易理解，可以把for循环去掉，改成

/* 情况1 */
cur.emplace_back(candidates[i]);
dfs(candidates, target - candidates[i], i, cur, res);
/* 情况2 */
cur.pop_back();
dfs(candidates, target, i + 1, cur, res);

不过这样会增加递归次数，但结果也对。

Combination Sum II

原题链接Combination Sum II

上面的扩展，序列中可以有重复元素，求所有和为target的集合。
这里主要是解决集合重复问题，比如示例中的序列有两个1，那么第一个1和2,5构成的集合满足条件，第2个1和2,5构成的集合也满足条件，但是[1,2,5]这个集合不可以重复出现，所以结果中只有一个[1,2,5]。

思路还是和上面一样，深度优先（dfs），但是需要解决重复问题，一种方法是用一个std::set>存储所有已找到的集合，在添加新集合之前判断一下是否在set中出现过，但是这种方法仍然需要把所有重复的集合都遍历出来，比较慢，有什么方法可以在摇篮里扼杀掉重复集合的出现呢。
因为在每层递归中都是在for循环中选择某一个，然后开启下层循环，所以可以尝试在for循环中判断当前选择的这个元素有没有递归下去的必要。
打个比方，为了直观，以[10,1,2,7,6,5,5,5]序列为例，排序后为[1,2,5,5,5,6,7,10]。这里把示例中的一个1换成两个5，为了让重复的那项在中间，更有一般性。

1. 假设最后找到的集合为a1,a2,…,5,…an，代表只从重复项中拿出一个元素的情况，显然在以第一个5开始的递归过程中就可以组成满足条件的集合，不需要考虑再从第二个5开始递归。
2. 假设最后找到的集合为a1,a2,…,5,5,…an，代表从重复项中拿出多个元素的情况，那么第二个5也在从第一个5开始的递归过程中找到了。当然也不需要从第二个5开始递归从而和第三个5组成一样的集合。

所以无论是在所有的5中选择一个，还是选择某些个5，都只需要考虑重复项的第一个元素。
代码如下

class Solution {
public:vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {std::sort(candidates.begin(), candidates.end());vector<vector<int>> res;vector<int> cur;dfs(candidates, target, 0, res, cur);return res;}
private:void dfs(vector<int>& candidates, int target, int idx, vector<vector<int>>& res, vector<int>& cur){if(target == 0)res.push_back(cur);if(idx >= candidates.size() || candidates[idx] > target)return;for(int i = idx; i < candidates.size(); ++i){if(candidates[i] > target)break;/* 对于后续重复的元素，都不需要在考虑，因为已经在重复元素的第一个元素的递归过程中都找到了 */if(i > idx && candidates[i] == candidates[i - 1])continue;cur.emplace_back(candidates[i]);dfs(candidates, target - candidates[i], i + 1, res, cur);cur.pop_back();}}
};

Combination Sum III

原题链接Combination Sum III

和前面的要求不太一样，本题要求最后的集合的个数为k，每个元素都在1-9这个范围，同时每个元素不能在一个集合中出现多次。
这个就直接用上面的方法找就可以了

class Solution {
public:vector<vector<int>> combinationSum3(int k, int n) {vector<vector<int>> res;vector<int> cur;dfs(k, n, 1, cur, res);return res;}
private:/* k表示还可以选择几个数字，n表示还差多少，idx表示当前选择到的数字 */void dfs(int k, int n, int idx, vector<int>& cur, vector<vector<int>>& res){if(k == 0 && n == 0){res.emplace_back(cur);return;}if(k == 0)return;for(int i = idx; i < 10; ++i){cur.emplace_back(i);dfs(k - 1, n - i, i + 1, cur, res);cur.pop_back();}}
};

Combination Sum IV

原题链接Combination Sum IV

一个结果集合中同一个数字可以出现多次，顺序不同的集合算作不同的结果，返回有多少种可能的集合。
因为每次递归都可以选择给定序列的每一个元素，所以如果每次递归都遍历一遍给定序列的话，唔…超时了…为什么会超时，当然是过多的重复计算了，对于某个剩余大小n，不同的遍历过程可能是相同的。比如说某次递归要计算和为n的序列有多少个，下次又有另一个递归也要计算和为n的序列有多少个，这就造成了重复计算
怎么解决呢，当然动态规划了，解决重复计算是动态规划的设计初衷啊，这里没要求把所有集合都找到，只是找个数，用动态规划自然比较轻松。

代码如下

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {std::sort(nums.begin(), nums.end());vector<int> dp(target + 1, -1);return dfs(nums, target, dp);   }
private:int dfs(vector<int>& nums, int target, vector<int>& dp){/* * 如果计算过和为target的集合个数，直接返回 * dp[target]代表和为target的集合序列有多少个*/if(dp[target] != -1)return dp[target];int n = 0;if(target == 0){n = 1;}else{for(int i = 0; i < nums.size(); ++i){if(nums[i] > target)break;n += dfs(nums, target- nums[i], dp);}}dp[target] = n;return n;}
};

上面四道题都是形如给定一个序列，找到和为某个数的集合，主要使用的方法是深度优先遍历。难点在处理特殊情况上，比如解决重复集合问题，只考虑重复元素的第一个。再比如动态规划的使用，可以有效避免重复计算，提高效率。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！