LeetCode 77 组合 - 回溯解法
https://leetcode.cn/problems/combinations/description/
思路
这个是搜索算法， 递归函数没有返回值，所以要控制全局变量，而深层次的调用就不是取值了， 而是做某件事情.
一开始path为空， 选数加入path， 这里为1， 然后再从1后面的里面选数加入path. 不断重复上述过程. 所以函数可以理解为 : 不断地从某一区间选值加入到path中. 这是一件事而非求值.
定义全局变量 path 表示已经得到的组合， result为最终返回的数组. 递归函数的语义是: 从start到max选一个数加入path， 或往path中加入新的值 . 那么， 当path的长度达到要求的长度时直接返回， 否则继续往path中加入新的值.
- 直接返回. path的长度达到要求的值.
- 进一步调用. 本层从start到max中选个数加入到path中， 有很多情况， 要用for 循环遍历， 循环内: path中加入i， (再从i+1到max中选个数加入到path中)是下一层调用.
可以看到， 求解递归问题时可以先手动模拟得到 不变的流程， 上述题目中为 “不断地从某一区间选一个数加入到path中”， 这个不变的流程就是递归函数的语义.
function add_path(start , max){ //从start 到max选值加入到path中.
if(path.size()==) result.add(path) return
// 进一步调用
// 显然, 一开始往path中加入的值有1-n, n种情况 ,这里1应作为参数传入, 后续为i-n 个情况
// 每种情况都要遍历到位, for循环
for(i=start, i<=max, i++){
path.push_back(i) //加入i本层选的数
// 加入i后 ,再选数加入path时, 就要选i后面的数了.
add_path(i+1,max) //从i+1到max 选数加入
// 因为用了for循环且path为全局变量, 因此要及时清理path种的值
path.pop_back()
}
}
代码
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
void search(int max,int start,int num_k){ //意为从start 到max选值加入path
if(path.size()==num_k){
result.push_back(path);
return;
}
for(int i =start;i<=max;i++){ //从start 开始遍历
path.push_back(i); //加入到path中
search(max,i+1,num_k); //从下一位到max选值加入到path中.
path.pop_back(); //清理全局变量path
}
}
vector<vector<int>> combine(int n, int k) {
search(n,1,k);
return result;
}
};
选或不选
这里没有剪枝。
class Solution {
public:
vector<int> path;
vector<vector<int>> result;
void sel_or_not(int i,int k,int n){
if(path.size()==k){
result.push_back(path);
return;
}
if(i>n) return;
path.push_back(i);
sel_or_not(i+1,k,n);
path.pop_back();
sel_or_not(i+1,k,n);
}
vector<vector<int>> combine(int n, int k) {
sel_or_not(1,k,n);
return result;
}
};