摘要
本文主要介绍了回溯算法的理论基础和回溯法模版，以及LeetCode中77.组合问题的解题思路和代码。
1、回溯算法理论基础
1.1 概念
回溯算法是一种用于解决组合问题、排列问题和搜索问题的常用算法。它基于深度优先搜索的思想，通过不断地尝试各种可能的选择，然后回退到上一步，直到找到问题的解或穷尽所有可能性。
回溯算法的核心思想是构建一棵决策树，每个节点表示在问题中的一个决策点，从根节点出发，逐步向下扩展树，直到找到解或无法继续扩展。如果遇到无法继续扩展的情况，就回退到上一层节点，尝试其他分支。
以下是回溯算法的基本框架和关键要点：
下面是一个简单的 Java 示例，用于解决组合问题（找到数组中所有可能的组合）：
import java.util.ArrayList;
import java.util.List;
public class BacktrackingExample {
public List combine(int n, int k) {
List result = new ArrayList();
List path = new ArrayList();
backtrack(result, path, n, k, 1);
return result;
}
private void backtrack(List result, List path, int n, int k, int start) {
// 结束条件：已选择的元素数量达到 k
if (path.size() == k) {
result.add(new ArrayList(path));
return;
}
// 选择列表：从 start 到 n 中选择一个数加入当前组合
for (int i = start; i n 时，表示已经考虑完了所有可选数字，直接返回。
进行选择和递归： 在递归函数的主体部分，我们需要考虑两种情况：
- 选择当前数字
i，将其添加到当前组合中，然后递归调用函数，传递参数i+ 1和k - 1。 - 不选择当前数字
i，直接递归调用函数，传递参数i+ 1和k。
撤销选择： 在每一次递归返回后，需要撤销选择，即将当前数字从组合中移除，以便考虑下一个数字的选择。
回溯搜索： 通过不断地进行选择和递归，回溯算法会搜索所有可能的组合。
1、可以剪枝优化吗？
例如，对于给定的参数
n = 4, k = 2，当遍历选择列表时，需要考虑k的值来确定循环的范围。具体来说，当k = 2时，如果n = 3，我们可以继续遍历，但如果n = 4，则不应该继续遍历。因此，我们可以调整循环变量i的取值范围为[start, (n - k + 1) + linked.size()]。这个调整确保了在当前状态下，仅考虑那些可以生成有效组合的数字。这是一个很好的优化，以减少不必要的遍历，加快算法的执行速度。
2.2 代码
未剪枝优化
public List combine(int n, int k) {
List list = new ArrayList();
LinkedList linked = new LinkedList();
combine(list, linked, n, k, 1);
return list;
}
public void combine(List list, LinkedList linked, int n, int k, int start) {
if(linked.size() == k) {
list.add(new ArrayList(linked));
return;
}
for(int i=start; i
