回溯
输入“/”快速插入内容
回溯
回溯
回溯法一般可以解决如下几种问题：
•
组合问题：N个数里按一定规则找出k个数的集合
•
切割问题：一个字符串按一定规则有几种切割方式
•
子集问题：一个N个数的集合里有多少符合条件的子集
•
排列问题：N个数按一定规则全排列，有几种排列方式
•
棋盘问题：N皇后，解数独等
回溯算法模板
代码块
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
组合
代码块
class Solution {
List<List<Integer>> resList = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
backTracing(n,k,1);
return resList;
}
private void backTracing(int n,int k,int startIndex){
if (path.size() == k){
resList.add(new ArrayList<>(path));
return;
}
//剪枝由i<=n 变为 i<=n - (k - path.size()) + 1
for (int i = startIndex;i <= n - (k - path.size()) + 1;i++){
path.add(i);
backTracing(n,k,i + 1);
path.remove(path.size() - 1);
}
}
}