主要内容 #
- 组合问题
- 求解方法
- 回溯三部曲
- 参考代码
1. 组合问题 #
给定两个整数 n 和 k,返回 1 … n 中所有可能的 k 个数的组合。
输入描述
输入两个正整数n和k。
输出描述
输出所有的k个数的组合。
输入输出示例
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
2. 求解方法 #
2.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循环,是不是开始窒息。
此时就会发现虽然想暴力搜索,但是用for循环嵌套连暴力都写不出来!
2.2 回溯法求解 #
回溯法解决的问题都可以抽象为树形结构(N叉树)那么把组合问题抽象为如下树形结构:
可以看出这个棵树,一开始集合是 1,2,3,4, 从左向右取数,取过的数,不再重复取。
第一次取1,集合变为2,3,4 ,因为k为2,我们只需要再取一个数就可以了,分别取2,3,4,得到集合[1,2] [1,3] [1,4],以此类推。
每次从集合中选取元素,可选择的范围随着选择的进行而收缩,调整可选择的范围。
图中可以发现n相当于树的宽度,k相当于树的深度。
那么如何在这个树上遍历,然后收集到我们要的结果集呢?
图中每次搜索到了叶子节点,我们就找到了一个结果。
相当于只需要把达到叶子节点的结果收集起来,就可以求得 n个数中k个数的组合集合。
3. 回溯三部曲 #
递归函数的返回值以及参数
在这里要定义两个全局变量,一个用来存放符合条件单一结果,一个用来存放符合条件结果的集合。
代码如下:
vector < vector < int >> result; // 存放符合条件结果的集合 vector <int>path; // 用来存放符合条件结果
函数里一定有两个参数,既然是集合n里面取k的数,那么n和k是两个int型的参数。
然后还需要一个参数,为int型变量startIndex,这个参数用来记录本层递归的中,集合从哪里开始遍历(集合就是[1,…,n] )。
为什么要有这个startIndex呢?
每次从集合中选取元素,可选择的范围随着选择的进行而收缩,调整可选择的范围,就是要靠startIndex。
从下图中红线部分可以看出,在集合[1,2,3,4]取1之后,下一层递归,就要在[2,3,4]中取数了,那么下一层递归如何知道从[2,3,4]中取数呢,靠的就是startIndex。
所以需要startIndex来记录下一层递归,搜索的起始位置。
那么整体代码如下:
vector < vector < int >> result; // 存放符合条件结果的集合 vector <int>path; // 用来存放符合条件结果 void backtracking(int n, int k, int startIndex)
回溯函数终止条件
path这个数组的大小如果达到k,说明我们找到了一个子集大小为k的组合了,在图中path存的就是根节点到叶子节点的路径。
此时用result二维数组,把path保存起来,并终止本层递归。
所以终止条件代码如下:
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(); // 回溯,撤销处理的节点 }
可以看出backtracking(递归函数)通过不断调用自己一直往深处遍历,总会遇到叶子节点,遇到了叶子节点就要返回。
4. 参考代码 #
#include<iostream> #include<vector> using namespace std; 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) { result.clear(); // 可以不写 path.clear(); // 可以不写 backtracking(n, k, 1); return result; } }; int main(){ int n, k; cin >> n >> k; Solution solution; vector<vector<int> > ans; ans = solution.combine(n, k); cout << endl; for(int i = 0; i < ans.size(); i++){ // 结果输出 for(int j = 0; j < k; ++j){ cout << ans[i][j] << " "; } cout << endl; } return 0; }