参考链接代码随想录 (programmercarl.com)
一、回溯算法基础
1.什么是回溯法？
回溯是递归的副产品，只要有递归就会有回溯。
2. 回溯法的效率
因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。
那么既然回溯法并不高效为什么还要用它呢？
因为没得选，一些问题能暴力搜出来就不错了，撑死了再剪枝一下，还没有更高效的解法。
此时大家应该好奇了，都什么问题，这么牛逼，只能暴力搜索。
3.回溯法解决的问题
回溯法，一般可以解决如下几种问题：
- 组合问题：N个数里面按一定规则找出k个数的集合
- 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个N个数的集合里有多少符合条件的子集
- 排列问题：N个数按一定规则全排列，有几种排列方式
- 棋盘问题：N皇后，解数独等等
二、组合问题
重点概括：
- 如果解决一个问题有多个步骤，每一个步骤有多种方法，题目又要我们找出所有的方法，可以使用回溯算法；
- 回溯算法是在一棵树上的 深度优先遍历（因为要找所有的解，所以需要遍历）；
- 组合问题，相对于排列问题而言，不计较一个组合内元素的顺序性（即 [1, 2, 3] 与 [1, 3, 2] 认为是同一个组合），因此很多时候需要按某种顺序展开搜索，这样才能做到不重不漏。
回溯算法首先需要画出递归树，不同的树决定了不同的代码实现。下面给出了两种画树的思路。
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
public class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<>();
if (k <= 0 || n < k) {
return res;
}
//创建一个双端队列path，用于存储当前生成的组合。调用dfs方法进行递归生成组合。
Deque<Integer> path = new ArrayDeque<>();
//dfs方法是一个递归函数，用于生成组合。它有五个参数：n表示数字的范围，k表示组合的长度，index表示当前数字的索引，path表示当前生成的组合，res表示最终的结果列表。
dfs(n, k, 1, path, res);
return res;
}
private void dfs(int n, int k, int index, Deque<Integer> path, List<List<Integer>> res) {
//终止条件的判断。如果当前生成的组合长度等于k，则将其添加到最终结果列表res中，并返回。
if (path.size() == k) {
res.add(new ArrayList<>(path));
return;
}
// 只有这里 i <= n - (k - path.size()) + 1 与参考代码 1 不同; 在回溯的基础上进行剪枝
for (int i = index; i <= n - (k - path.size()) + 1; i++) {
//这段代码使用了深度优先搜索（DFS）的思想，通过递归生成所有可能的组合。组合生成的过程中，使用双端队列path来保存当前生成的组合，并将符合条件的组合添加到最终结果列表中。
path.addLast(i);
dfs(n, k, i + 1, path, res);
path.removeLast();
}
}
}
