来自百度百科的解释:回溯,计算机算法,回溯法也称试探法,它的基本思想是:从问题的某一种状态(初始状态)出发,搜索从这种状态出发所能达到的所有“状态”,当一条路走到“尽头”的时候(不能再前进),再后退一步或若干步,从另一种可能“状态”出发,继续搜索,直到所有的“路径”(状态)都试探过。这种不断“前进”、不断“回溯”寻找解的方法,就称作“回溯法”。
常见的回溯问题有组合、排列、子集、分割和棋盘问题等。下面给出回溯算法的模板。
private void backtracking(参数1,参数2,...){
if(递归终止条件){
收集结果;
return;
}
for(遍历集合){
处理;
backtracking(参数1,参数2,...); // 递归;
回溯;
}
}
组合
给定两个整数 n 和 k,返回 1 … n 中所有可能的 k 个数的组合。
示例 1:
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
class Solution {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
backtracking(n, k, 1);
return ans;
}
void backtracking(int n, int k, int startIndex){
// 递归终止条件
if(path.size() == k){
ans.add(new ArrayList<>(path));
return;
}
// for循环遍历集合,这里的集合为[1, 2, 3, ..., n]
for(int i = startIndex;i <= n;i++){
// 处理
path.add(i);
// 递归
backtracking(n, k, i + 1);
// 回溯
path.remove(path.size() - 1);
}
}
}
根据上述示例,详细说明上述代码的执行过程。首先定义收集所有组合的ans集合,定义一个集合path用于收集某个组合,如果符合条件,将其放入ans集合中。combine调用backtracking方法,最后返回ans集合。接下来,详细说明backtracking的执行过程。
path为空,不符合if条件,进入for循环,i = startIndex = 1。将1放入集合path中,path为[1]。递归进入下一个backtracking中。path长度为1,不满足if,此时startIndex为2,i从2开始,将2加入path中,此时path为[1, 2],递归进入下一个backtracking中,满足if条件要求的path长度为2,将[1,2]放入ans集合中,并返回。返回到上一个backtracking中,执行回溯,将path最后一个元素2移除,path为[1]。继续执行for循环,刚开始startIndex为2,i从2开始,现在i++后,i等于3,将3放入path集合中,path为[1, 3]。递归进入下一个backtracking中,此时path长度为2,满足if要求的条件,将[1, 3]放入ans集合中,返回到上一个backtracking,执行回溯条件,将元素3从path中移除,path为[1]。继续执行for循环,i为4,将元素4放入path集合中,path为[1, 4],递归进入下一个backtracking中,此时path长度为2,满足if条件,将[1, 4]放入ans中,并返回到上一个backtracking,将4从path中移除。此时for循环遍历完成,backtracking执行完成,返回最开始的trackbacking,将元素1从集合中移除。path为空。
继续执行for循环,i++后,i为2,将元素2加入path中,此时path为[2]。进入下一个backtracking中,startIndex为3,将元素3加入path中,path为[2, 3],递归进入下一个backtracking中,满足if条件,将[2, 3]加入ans集合中,递归返回上一个backtracking,将元素3从path集合中移除,path为[2]。i++,i为4,将元素4放入path中,path为[2, 4]。递归进入下一个backtracking中,path满足if条件,将[2, 4]放入ans集合中,并返回上一个backtracking,将4从path中移除,此时for循环遍历完成,递归返回最初的backtracking,将元素2从path中移除。
继续执行for循环,将元素3加入到path中,path为[3],递归进入下一个backtracking,startIndex为4,因此i等于4,将元素4加入到path中,此时path为[3, 4],递归进入下一个backtracking中,满足if条件,将[3, 4]加入ans集合,递归返回上一个backtracking,将元素4从path中移除,path为[3],此时for循环遍历结束,返回到最初的backtracking中,将元素3从path集合中移除,path为空。
继续执行for循环,将元素4加入到path中,path为[4],递归进入下一个backtracking,此时startIndex为5,大于4,不进入for循环,递归返回最初的for循环,i++,大于4,最初backtracking方法的for循环执行结束,返回到combine方法中,并返回ans。
在上述代码中,backtracking方法中传入startIndex参数,用于标记下一轮for循环应该从哪个元素开始遍历。还可以发现在最初for循环遍历到元素4时,起始没有必要继续递归下去,也就是说集合中剩余元素小于题目要求的组合数k减去path的长度时,可以直接返回,这就是剪枝操作,去掉不必要的遍历。
class Solution {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
backtracking(n, k, 1);
return ans;
}
void backtracking(int n, int k, int startIndex){
// 剪枝
if(n - startIndex + 1 < k - path.size()){
return;
}
// 递归终止条件
if(path.size() == k){
ans.add(new ArrayList<>(path));
return;
}
// for循环遍历集合,这里的集合为[1, 2, 3, ..., n]
for(int i = startIndex;i <= n;i++){
// 处理
path.add(i);
// 递归
backtracking(n, k, i + 1);
// 回溯
path.remove(path.size() - 1);
}
}
}
参考:带你学透回溯算法(理论篇)| 回溯法精讲!