Combination Sum问题 在leetcode的有一系列题目 采用dfs 回溯的方法求解，当然代码仍需优化，剪枝是个重点 需要仔细弄懂最初的第一题，后面的就是各种调整了 39 Combination Sum（https://leetcode.com/problems/combination-sum/）
Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. For example, given candidate set [2, 3, 6, 7] and target 7, A solution set is:
[ [7], [2, 2, 3] ]此题的搜索树如下
此题最终的ac代码
class Solution { private: vector<vector<int>> ans; vector<int> rs; public: void dfs(int nowIndex,int nowSum, vector<int> cand, int candSize, int target) { if (nowSum > target) return; if (nowSum == target) { ans.push_back(rs); return; } for (int i = nowIndex; i < candSize; i++){ if (nowSum + cand[i] <= target) // 因为cand是排序好的，显然会有大量的重复，应该避免，相当于剪枝 { rs.push_back(cand[i]); dfs(i, nowSum + cand[i], cand, candSize, target); rs.pop_back();// 回溯 } else continue; } } vector<vector<int>> combinationSum(vector<int>& candidates, int target) { int len = candidates.size(); if (len == 0) return ans; sort(candidates.begin(), candidates.end());// 排序 dfs(0,0, candidates,len, target); return ans; } };题目地址 https://leetcode.com/problems/combination-sum-ii/
在dfs之前，数据是排好序的，但是会有连续相同数字出现的情况，计算是会有重复的？？？
注意一个问题: 下面的两个if在代码中的顺序不要颠倒， why?
if(curSum == tar) { for(int i=0;i<(int)ans.size();i++) cout << ans[i] << " "; cout << endl; rs.push_back(ans); return; } if(curIndex >= candiLen || curSum > tar) return;去重条件就一个if, why
在上一题的基础上，保证数组中的每个数字不能够重复计算，所以需要设计去重的功能，在dfs时做了修改，发现仍然重复，所以有用到了c++stl map结构去重
最终的ac代码：
class Solution { private: map<vector<int>, int> mp; vector<vector<int>> ans; vector<int> rs; public: void dfs(int nowIndex,int nowSum, vector<int> cand, int candSize, int target) { if (nowSum > target) return; if (nowSum == target) { // 因为仍然会有重复，利用map/set去重 if (mp[rs] == 0) { ans.push_back(rs); mp[rs] = 1; } return; } // 从当前的下一个开始，不包括自己，因为每个数组中的数字 for (int i = nowIndex + 1; i < candSize; i++){ if (nowSum + cand[i] <= target) // 因为cand是排序好的，显然会有大量的重复，应该避免，相当于剪枝 { rs.push_back(cand[i]); dfs(i, nowSum + cand[i], cand, candSize, target); rs.pop_back();// 回溯 } else continue; } } vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { int len = candidates.size(); if (len == 0) return ans; sort(candidates.begin(), candidates.end());// 排序 dfs(-1,0, candidates,len, target); return ans; } };题目地址 https://leetcode.com/problems/combination-sum-iii/
有了上面两题的求解思路和基础，这题基本上就是个自我变化的过程。不过若一开始就给出这题，应该也能想到类似的方法
ac代码
class Solution { private: vector<vector<int>> ans; vector<int> rs; public: void dfs(int nowIndex,int nowSum, vector<int> cand, int candSize, int target,int nowRsSize,int k) { if (nowSum > target || nowRsSize > k) return; if (nowSum < target && nowRsSize == k) return; if (nowSum == target && nowRsSize == k) { ans.push_back(rs); return; } // 从当前的下一个开始，不包括自己，因为每个数组中的数字 for (int i = nowIndex + 1; i < candSize; i++){ if (nowSum + cand[i] <= target && nowRsSize <= k) // 因为cand是排序好的，显然会有大量的重复，应该避免，相当于剪枝 { rs.push_back(cand[i]); dfs(i, nowSum + cand[i], cand, candSize, target,nowRsSize+1,k); rs.pop_back();// 回溯 } else continue; } } vector<vector<int>> combinationSum3(int k, int n) { vector<int> candidates{ 1, 2, 3, 4, 5, 6, 7, 8, 9 }; dfs(-1,0, candidates,9, n,0,k); return ans; } };https://leetcode.com/submissions/detail/78260609/
Given two integers n and k, return all possible combinations of k numbers out of 1 … n.
For example, If n = 4 and k = 2, a solution is:
[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]采用递归方式求解，因为数字不会重复，长度也限定了，思路同前面几题
ac代码如下
class Solution { private: vector< vector<int> >ans; vector<int> v; public: void dfs(int n, int k, int nowK, int indexN) { if (nowK > k) return; if (nowK == k) { /*for (int i = 0; i < k; i++) cout << v[i] << " "; cout << endl;*/ ans.push_back(v); return; } for (int i = indexN; i <= n; i++) { v.push_back(i); dfs(n, k, nowK + 1, i + 1); v.pop_back(); } } vector<vector<int>> combine(int n, int k) { dfs(n, k, 0, 1); return ans; } };https://leetcode.com/problems/combination-sum-iv/
Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
Example:
nums = [1, 2, 3] target = 4 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. Therefore the output is 7.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?
采用dfs会超时，此题结果是很大的，因为数字可以重复，任意组合
应采用动态规划的方法
class Solution { public: int combinationSum4(vector<int>& nums, int target) { int len = nums.size(); sort(nums.begin(), nums.end()); vector<int> dp(target + 1, 0); // dp[i] 表示 能组成 等于i的个数 dp[i - num] + num 可以凑成 dp[i] dp[0] = 1; for (int i = 1; i <= target; i++) { for (int j = 0; j < len; j++) { if (nums[j] <= i) dp[i] += dp[i - nums[j]]; else break; } } return dp[target]; } };