77. 组合
题目描述
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：
输入：n = 4, k = 2 输出： [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
示例 2：
输入：n = 1, k = 1 输出：[[1]]
思路分析
直接的解法是使用for循环，例如示例中k为2，很容易想到 用两个for循环，这样就可以输出 和示例中一样的结果。
int n = 4; for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { cout << i << " " << j << endl; } }
n = 100, k = 3 那么就三层for循环，代码如下：
int n = 100; for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { for (int u = j + 1; u <= n; n++) { cout << i << " " << j << " " << u << endl; } } }
但是如果n为100,k为50,那就是50层for循环,无语住了…
于是,我们可以尝试使用回溯法,本质就是 循环+递归,从而实现多层循环
回溯法解决的问题都可以抽象为树形结构（N叉树），用树形结构来理解回溯就容易多了。
由下图可知:元素的个数n等于树的宽度,k等于树的深度
算法设计
- 每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围。
- 图中每次搜索到了叶子节点，我们就找到了一个结果。
- 只需要把达到叶子节点的结果收集起来，就可以求得 n个数中k个数的组合集合。
卡尔大佬的回溯法三部曲
递归函数的返回值以及参数
这里直接使用全局变量来操作,一个存放最终的结果集,一个存放符合条件的临时集合.这样我们也就不需要返回值了.
参数:数据个数n,组合个数k 每次需要传入.另外也需要传入下次循环的起始位置,方便下一次其他数据进行组合.
vector<int> path; vector<vector<int>> result; void backtracking(int n,int k,int startIndex){ ... }
- 回溯函数终止条件
当path.size() == k了,则说明我们已经找到了大小为k的组合了. 结束递归
if(path.size()==k){ result.push_back(path); return;//结束递归 }
- 单层搜索过程
回溯法的搜索过程就是一个树型结构的遍历过程，在如下图中，可以看出for循环用来横向遍历，递归的过程是纵向遍历。
for循环每次从startIndex开始遍历，然后用path保存取到的节点i,递归回来之后进行回溯,继续循环.
for (int i = startIndex; i <= n; i++) { // 控制树的横向遍历 path.push_back(i); // 处理节点 backtracking(n, k, i + 1); // 递归：控制树的纵向遍历，注意下一层搜索要从i+1开始 path.pop_back(); // 回溯，撤销处理的节点 }
代码优化
可以剪枝的地方在递归中每一层的for循环条件处。
如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。
已经选择的元素个数：path.size();
还需要的元素个数为: k - path.size();
在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历
为什么有个+1呢，因为包括起始位置。
所以中间for循环的条件可以改造为:i <= n-(k-path.size())+1
参考代码
#include<bits/stdc++.h> using namespace std; vector<int> path; vector<vector<int>> result; void backtracking(int n,int k,int startIndex){ if(path.size()==k){ result.push_back(path); return;//结束递归 } // for(int i = startIndex; i <= n;i++){//未剪枝 for(int i = startIndex; i <= n-(k-path.size())+1;i++){ //剪枝 path.push_back(i);//存放i元素 backtracking(n,k,i+1);//减小可选择返回,继续递归 path.pop_back();//弹出当前元素,进行回溯 } } vector<vector<int>> combine(int n, int k) { backtracking(n,k,1); return result; }
216.组合总和III
题目描述
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：
所有数字都是正整数。
解集不能包含重复的组合。
示例 1:
输入: k = 3, n = 7 输出: [[1,2,4]]
示例 2:
输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]
思路分析
本题相对于上个题只是多个 之和为n的限制,其他的处理思路和上题类似
转为树形图就是:k相当于树的深度. 1-9 相当于树的宽度
下面开始我们熟悉的回溯三部曲
确定递归参数和返回值
递归参数:每次需要传入组合的位数 k,循环的下一个位置下标 index,当前组合数的和 sum,目标值 targetSum
确定递归的结束条件
当path.size()==k时结束递归.但同时满足sum == targetSum,当前组合数才被加入到结果集中
确定单层递归的逻辑
先循环,加入元素,之后继续递归,递归之后进行回溯,回溯完毕进入下一次循环
算法剪枝
如果后序可选择的元素+当前组合数元素 小于 k,则没必要继续寻找了
如果组合数的和已经大于targetSum,则没必要再去寻找了.
参考代码
#include<bits/stdc++.h> using namespace std; vector<int> path; vector<vector<int>> result; void backtracking(int k,int startIndex,int sum,int targetSum) { if(sum>targetSum) {//剪枝 return; } if(path.size()==k) { if(sum==targetSum) { result.push_back(path); } return;//结束递归 } // for(int i = startIndex; i <= n;i++){ for(int i = startIndex; i <= 9-(k-path.size())+1; i++) { //此时还需要的元素大小 && path.push_back(i);//存放i元素 backtracking(k,i+1,sum+i,targetSum);//减小可选择返回,继续递归 这里返回的是i+1哦,和startIndex无关.. path.pop_back();//弹出当前元素,进行回溯 } } vector<vector<int>> combinationSum3(int k, int n) { backtracking(k,1,0,n); return result; }
17. 电话号码的字母组合
题目描述
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母
示例 1：
输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = "" 输出：[]
示例 3：
输入：digits = "2" 输出：["a","b","c"]
提示：
0 <= digits.length <= 4
digits[i] 是范围 [‘2’, ‘9’] 的一个数字。
思路分析
输入：“23”，抽象为树形结构，如图所示：
图中可以看出遍历的深度就是输入的 字符串的长度，而叶子节点就是我们要收集的结果，宽度为 字符所对应的字符串长度 ,如2==>abc
回溯三部曲
确定递归参数和返回值
参数:需要传入输入的字符串digits,当前递归到的digits的index
返回值:依旧定义两个个全局变量,一个是最终结果集,一个存放临时组合数.所以返回值为void 可以看出回溯类型的递归通常没有返回值
确定递归结束条件
如果index==digits.size(),则说明已经找到了满足的组合数,递归结束
确定单层递归逻辑
先从递归的index拿到对应的字符串,然后开始循环,递归,回溯…
参考代码
vector<string> result; string s; string arr[10] = { "",//0 "",//1 "abc",//2 "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz", }; void backtracking(string& digits,int index) {//digits:记录输入的数字 ,index:遍历前面的数字 if(digits.size()==index) { result.push_back(s); return; } int num = digits[index] - '0'; string temp = arr[num]; for(int i = 0; i < temp.size(); i++) { //每层遍历的都是digits中的元素 递归树的深度就是digits.size()大小 s.push_back(temp[i]); backtracking(digits,index+1); s.pop_back(); } } vector<string> letterCombinations(string digits) {//digits.size()==>k 循环次数 if(digits=="") {//注意digits为空的情况 return result; } backtracking(digits,0); return result; }
