一、组合
1.题目
. - 力扣(LeetCode)
2思路
把组合问题抽象成树形结构(N叉树)
每次从集合中选取元素,可选择的范围随着选择的进行而收缩,调整可选择的范围。
图中可以发现n相当于树的宽度,k相当于树的深度。
回溯法的搜索过程就是一个树型结构的遍历过程,在如下图中,可以看出for循环用来横向遍历,递归的过程是纵向遍历。
那么如何在这个树上遍历,然后收集到我们要的结果集呢?
图中每次搜索到了叶子节点,我们就找到了一个结果。
相当于只需要把达到叶子节点的结果收集起来,就可以求得 n个数中k个数的组合集合。
按照递归法写法去写回溯法即可。
1.递归函数的返回值以及参数
函数里一定有两个参数,既然是集合n里面取k个数,那么n和k是两个int型的参数。
然后还需要一个参数,为int型变量startIndex,这个参数用来记录本层递归的集合从哪里开始遍历,防止取到重复值。
2.回溯函数终止条件
path这个数组的大小如果达到k,说明我们找到了一个子集大小为k的组合了,在图中path存的就是根节点到叶子节点的路径。
3.单层搜索的过程
for循环每次从startIndex开始遍历,然后用path保存取到的节点i。
可以看出backtracking(递归函数)通过不断调用自己一直往深处遍历,总会遇到叶子节点,遇到了叶子节点就要返回。backtracking的下面部分就是回溯的操作了,撤销本次处理的结果。
总体代码:
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; 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;}
};
二、电话号码的字母组合
1.题目
17. 电话号码的字母组合 - 力扣(LeetCode)
2.思路
2.1 数字和字母如何映射
定义一个二维数组letterMap来映射。
同时需要把字符转换成数字
2.2 回溯法来解决n个for循环的问题
回溯三部曲:
1.传入参数
参数指定是有题目中给的string digits,然后还要有一个参数就是int型的index。这个index是记录遍历第几个数字了,就是用来遍历digits的(题目中给出数字字符串),同时index也表示树的深度。
2.终止条件
当遍历到字符串最后一个字符时,把子集加入到结果中。
3.单层遍历逻辑
把字符转换为数字,同时映射出字符串。用for循环进行遍历目前字符串。需要注意的是,每次遍历字符串从0开始,因为这道题是多个字符串的组合题。上面那题属于单个数组的组合题。
总体代码:
class Solution {
private:const string letterMap[10] = {"", // 0"", // 1"abc", // 2"def", // 3"ghi", // 4"jkl", // 5"mno", // 6"pqrs", // 7"tuv", // 8"wxyz", // 9};public:vector<string> result;string s;//index为处理的位数void backtracking(const string& digits,int index){if(index == digits.size()){result.push_back(s);return;}//转换成数字int digit = digits[index] - '0';string temp = letterMap[digit];for(int i = 0;i < temp.size();i++){s.push_back(temp[i]);backtracking(digits,index+1);s.pop_back();}}vector<string> letterCombinations(string digits) {if(digits.size() == 0) return result;backtracking(digits,0);return result;}
};
三、组合总和
1.题目
39. 组合总和 - 力扣(LeetCode)
2.思路
本题没有数量要求,可以无限重复,但是有总和的限制,所以间接的也是有个数的限制。为了不重复,只能往后取数字。
2.1 传入参数
除了原来给的两个参数candidate和target,另外加了sum和index。sum用来计算取的值总和大小,index用来标记for循环的开始位置。因为这道题属于单集和求组合。
2.2 终止条件
如果sum大于target,则回溯。
如果sum等于target,则加入result。
2.3 单层循环逻辑
sum加上当前值,并把当前值加入到path子集,进行下一步的元素寻找。大于或者等于则返回,进行回溯,同时sum要把当前值减掉。
总体代码:
class Solution {
public:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& candidates, int target,int sum,int index){if(sum > target) return;if(sum == target){result.push_back(path);return;}for(int i = index; i < candidates.size();i++){sum += candidates[i];path.push_back(candidates[i]);backtracking(candidates,target,sum,i);//递归path.pop_back(); //回溯sum -= candidates[i];}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {backtracking(candidates,target,0,0);return result;}
};