一、回溯知识
1.题目分类
2.回溯模板
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
二、算法题
77. 组合
1.未剪枝优化
class Solution {
List<List<Integer>> result=new ArrayList<>();
List<Integer> path=new LinkedList<>();
public List<List<Integer>> combine(int n, int k) {
backtracking(n, k, 1);
return result;
}
public void backtracking(int n,int k,int startindex){
//回溯函数终止条件
if(path.size()==k){
//当path的大小与组合大小相同时，说明找到了题目要求的组合，是回溯终止的情况
result.add(new ArrayList<>(path));
return;
}
for(int i=startindex;i<=n;i++){
path.add(i);
backtracking(n, k, i+1);
path.removeLast();
}
}
}
- startIndex 为了防止出现重复的组合
- result.add(new ArrayList<>(path))这种写法是为了防止在后续的过程中对 `path` 对象的修改影响到已经加入 `result` 中的组合。
- 如果直接使用 `result.add(path)`，那么在后续的回溯过程中，当从 `path` 中移除元素时，已经加入 `result` 的组合也会受到影响，因为它们引用的是相同的 `path` 对象
- 通过使用 `new ArrayList<>(path)`，实际上是创建了 `path` 的一个副本，使得 `result` 中的组合与后续的回溯过程互相独立，避免了相互影响。
- 这样做是为了确保 `result` 中的组合是独立的，而不会因为后续回溯的修改而导致错误的结果。
2.剪枝优化
class Solution {
List<List<Integer>> result=new ArrayList<>();
List<Integer> path=new LinkedList<>();
public List<List<Integer>> combine(int n, int k) {
backtracking(n, k, 1);
return result;
}
public void backtracking(int n,int k,int startindex){
//回溯函数终止条件
if(path.size()==k){
//当path的大小与组合大小相同时，说明找到了题目要求的组合，是回溯终止的情况
result.add(new ArrayList<>(path));
return;
}
for(int i=startindex;i<=n-(k-path.size())+1;i++){
path.add(i);
backtracking(n, k, i+1);
path.removeLast();
}
}
}
只修改了循环中的i的判断条件
已经选择的元素个数：path.size();
还需要的元素个数为: k - path.size();
下一个选取的元素在集合n的起始位置 : n - (k - path.size()) + 1，开始遍历
比如
取了1后，n - (k - path.size()) + 1=2，下一个元素要从2开始选，直接选定开始元素为1，不再尝试取2，3，4为开头，然后进入下一层循环
为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。
举个例子，n
