这篇文章主要讲解了“C++回溯算法中组合的相关问题怎么解决”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“C++回溯算法中组合的相关问题怎么解决”吧!
回溯算法模板
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
处理节点;
backtracking(路径,选择列表); // 递归
回溯,撤销处理结果
}
}
回溯问题,最关键的是画出二叉树,遍历、剪枝问题都要通过直观的观察才能总结
一、组合
剪枝策略
已经选择的元素个数:path.size();
还需要的元素个数为: k - path.size();
在集合n中至多要从该起始位置 : n - (k - path.size()) + 1,开始遍历
class Solution { private: vector<vector<int>> result; vector<int> path; void backtracking(int n,int k,int startIndex){ if(path.size()==k){ result.push_back(path); return; } 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) { backtracking(n,k,1); return result; } };
二、组合总和III与组合总和
1.组合总和III
在组合的基础上,多了一个求和的操作,求和也可以剪枝
class Solution { private: vector<vector<int>> result; vector<int> path; void backtracking(int sum,int k,int n,int startIndex){ if(sum>n) return; if(path.size()==k){ if(sum==n) result.push_back(path); return; } for(int i=startIndex;i<=9-(k-path.size())+1;i++){ path.push_back(i); sum+=i; backtracking(sum,k,n,i+1); sum-=i; path.pop_back(); } } public: vector<vector<int>> combinationSum3(int k, int n) { backtracking(0,k,n,1); return result; } };
2.组合总和
本题与组合III的区别在于,不限制组合内数字的个数,且同一个数字可以无限制重复被选取,体现在代码上就是,向下递归的时候,i不变
class Solution { private: vector<int> path; vector<vector<int>> result; void backtracking(vector<int>& candidates, int target,int index,int sum){ if(sum>target) return; if(sum==target){ result.push_back(path); return; } for(int i=index;i<candidates.size();i++){ path.push_back(candidates[i]); sum+=candidates[i]; backtracking(candidates,target,i,sum); sum-=candidates[i]; path.pop_back(); } } public: vector<vector<int>> combinationSum(vector<int>& candidates, int target) { backtracking(candidates,target,0,0); return result; } };
3.组合总和II
本题和组合总和的区别在于,输入样例中含有重复元素时,输出样例不能有重复元素
同一条枝干上,元素可以相同;而不同的枝干则不能重复
即:横向遍历不能重复、纵向遍历可以重复
class Solution { private: vector<int> path; vector<vector<int>> result; void backtracking(vector<int>& candidates, int target,int index,int sum){ if(sum>target) return; if(sum==target){ result.push_back(path); return; } for(int i=index;i<candidates.size();i++){ if(i>index&&candidates[i]==candidates[i-1]) continue; path.push_back(candidates[i]); sum+=candidates[i]; backtracking(candidates,target,i+1,sum); sum-=candidates[i]; path.pop_back(); } } public: vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { sort(candidates.begin(),candidates.end()); backtracking(candidates,target,0,0); return result; } };
三、电话号码的字母组合
这题很好的考察了:for循环横向遍历、递归纵向遍历的知识点
class Solution { private: const string letterMap[10]={ "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" }; public: string path; vector<string> result; void backtracking(string digits,int index){ if(index==digits.size()){ result.push_back(path); return; } int digit=digits[index]-'0'; string letter=letterMap[digit]; for(int i=0;i<letter.size();i++){ path.push_back(letter[i]); backtracking(digits,index+1); path.pop_back(); } } vector<string> letterCombinations(string digits) { if(digits.size()==0) return result; backtracking(digits,0); return result; } };