class Solution { private: vector<vector<int>> result;//存放符合条件的结果结合 vector<int> path;//存放符合条件的单一结果 void backtracking(int n, int k, int startIndex) { //回溯的终止条件:如果path数组的大小刚好等于k,说明找到了一个符合条件的结果集,存放进去 if (path.size() == k) { result.push_back(path); return; } //for(int i=startIndex; i<=n; i++) { /*这个循环其实可以进行剪枝优化,因为你要求k个数的结合,那你之多也就只能遍历到结合剩下k个元素的位置,后面的遍历都是没有意义的,优化如下*/ for (int i=startIndex; i<=(n-(k-path.size())+1); i++) { path.push_back(i);//处理节点 backtracking(n, k, i+1);//递归,一直往里放,直到满足终止条件结束 path.pop_back();//回溯,撤销处理的节点 } } public: vector<vector<int>> combine(int n, int k) { result.clear(); path.clear(); backtracking(n, k, 1); return result; } };
class Solution { private: vector<vector<int>> result; // 用来存放结果 vector<int> path; // 用来存放一个满足条件的路径 void backtrackint(int k, int n, int sum, int startIndex) { if (sum == n) { // 如果和为n满足了条件 if (path.size() == k) // 如果满足k个数 result.push_back(path); // 将满足要求的一个路径path放进去 return; } if (sum > n) // 进行剪枝,如果当前的已经大于n了,再往下比n更大 return; for (int i = startIndex; i <= 9; i++) { path.push_back(i); // 处理当前 sum += i; backtrackint(k, n, sum, i+1); // 递归 sum -= i; path.pop_back(); // 回溯 } } public: vector<vector<int>> combinationSum3(int k, int n) { result.clear(); path.clear(); backtrackint(k, n, 0, 1); return result; } };
class Solution { private: unordered_map<int, string> letterMap = {{2, "abc"}, {3, "def"}, {4, "ghi"}, {5, "jkl"}, {6, "mno"}, {7, "pqrs"},{8, "tuv"}, {9, "wxyz"}}; public: vector<string> result; string s; void backtracking(const string& digits, int index) { if (index == digits.size()) {//每个组合的字符串当中有digits.size()个元素 result.push_back(s); return; } int digit = digits[index] - '0';//将index位置对应的字符转换成Int string letters = letterMap[digit]; //取出digit对应的字符集 for (int i=0; i<letters.size(); i++) { s.push_back(letters[i]); backtracking(digits, index+1); //递归,注意index+1,要处理下一个数字了 s.pop_back(); //回溯 } } vector<string> letterCombinations(string digits) { result.clear(); s.clear(); if (digits.size() == 0) { return result; } backtracking(digits, 0); return result; } };
class Solution { private: vector<vector<int>> result; vector<int> path; void backtracking(vector<int>& candidates, int target, int sum, int startIndex) { if (sum == target) { result.push_back(path); return; } if (sum > target) // 因为数组中元素都是正整数,所以可以剪枝 return; for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) { // &&后面的是剪枝,意思是在当前层中,如果下一层的sum(就是本层的sum加上candidates[i])已经大于target了,就没必要继续往下了 path.push_back(candidates[i]); sum += candidates[i]; backtracking(candidates, target, sum, i); // 这里的i是重点!!!体现了可以重复!!! sum -= candidates[i]; path.pop_back(); } } public: vector<vector<int>> combinationSum(vector<int>& candidates, int target) { result.clear(); path.clear(); if (candidates.empty()) return {}; sort(candidates.begin(), candidates.end()); backtracking(candidates, target, 0, 0); return result; } }; // 求和问题中,排序之后加剪枝是常见的套路! // 什么时候用startIndex,什么时候不用:如果是一个集合来求组合的话,就需要startIndex;如果是多个集合取组合,各个集合之间相互不影响,那么就不用startIndex // 元素可被无限重复选取表现在代码里 // 剪枝方法
class Solution { private: vector<vector<int>> result; vector<int> path; void backtracking(vector<int>& candidates, int target, int sum, int startIndex, vector<bool>& used) { if (sum == target) { result.push_back(path); return; } if (sum > target) { return; } for (int i=startIndex; i<candidates.size() && (sum + candidates[i]) <= target; i++) { /*如果candidates[i] == candidates[i-1]并且used[i-1] == 1的话,说明元素在同一个树枝里使用过,这是允许的 *如果candidates[i] == candidates[i-1]并且used[i-1] == 0的话,说明元素在同一树层里重复了,这是不允许的,要进行去重 */ if (i>0 && candidates[i] == candidates[i-1] && used[i-1] == false) { continue; } sum += candidates[i]; path.push_back(candidates[i]); used[i] = true; backtracking(candidates, target, sum, i+1, used); // 这里是i+1不是i used[i] = false; sum -= candidates[i]; path.pop_back(); } } public: vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { result.clear(); path.clear(); vector<bool> used(candidates.size(), false); // 用这数组来进行去重 sort(candidates.begin(), candidates.end()); // 先把数组排序,让相同的元素排在一起,这样才能后面去重 backtracking(candidates, target, 0, 0, used); return result; } };