网站背景色,遂宁住房和城乡建设厅网站,全屏网站,工程造价招聘网最新招聘组合问题#xff1a;集合内元素的组合#xff0c;不同集合内元素的组合 回溯模板伪代码
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择#xff1a;本层集合中元素#xff08;树中节点孩子的数量就是集合的大小#xff09;) {处理节点;backtrackin… 组合问题集合内元素的组合不同集合内元素的组合 回溯模板伪代码
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果}
}216.组合总和III
找出所有相加之和为 n 的 k 个数的组合且满足下列条件
只使用数字1到9每个数字 最多使用一次 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次组合可以以任何顺序返回。
思路
仍然是一个集合内元素的组合问题与77.组合相似
代码
class Solution {
public:vectorvectorint result;vectorint path;int sum 0;void backtracking(int k, int n, int startIndex) {if(sum n) return; //剪枝因为相加后面只可能大于n故不再遍历if(path.size() k) {if(sum n) {result.push_back(path);}return;}for(int i startIndex; i 9 - (k - path.size()) 1; i) { //剪枝k - path.size()还需要纵向遍历的层数 后面的子集合内元素不足path.push_back(i);sum i;backtracking(k, n, i1);//回溯 撤销处理结果path.pop_back();sum - i;}}vectorvectorint combinationSum3(int k, int n) {result.clear();path.clear();backtracking(k, n, 1);return result;}
};17.电话号码的字母组合
给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。
思路
与216.组合总和III不同这是不同集合内元素组合的问题。
横向遍历是针对当前号码对应的字符集遍历该字符集的所有元素纵向遍历是针对下一个号码对应的字符集合遍历下一个字符集 而不是当前字符集的子集 class Solution {
public://因为本题每一个数字代表的是不同集合也就是求不同集合之间的组合//而77. 组合 (opens new window)和216.组合总和III (opens new window)都是求同一个集合中的组合vectorstring result;string path;vectorstring Str { , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz};void backTracking(string digits, int startIndex) {if(path.size() digits.size()) {result.push_back(path);return;}int digit digits[startIndex] - 1; string s Str[digit]; // 获取号码对应的字符集//横向遍历是针对当前号码对应的字符集纵向遍历是针对其它集合for(int i 0; i s.size(); i) {path.push_back(s[i]);backTracking(digits, startIndex1); // 纵向遍历递归注意index1针对下一个号码对应的字符集合path.pop_back();}}vectorstring letterCombinations(string digits) {result.clear();path.clear();if(digits.size() 0) return result; backTracking(digits, 0);return result;}
};
