什么叫回溯算法，一看就会，一写就废 _回溯算法

什么叫回溯算法对于回溯算法的定义，百度百科上是这样描述的：回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点” 。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
看明白没，回溯算法其实就是一个不断探索尝试的过程，探索成功了也就成功了，探索失败了就在退一步，继续尝试…… ，
组合总和组合总和算是一道比较经典的回溯算法题，其中有一道题是这样的。
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：

所有数字都是正整数。
解集不能包含重复的组合。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

这题说的很明白，就是从1-9中选出k个数字，他们的和等于n ，并且这k个数字不能有重复的。所以第一次选择的时候可以从这9个数字中任选一个，沿着这个分支走下去，第二次选择的时候还可以从这9个数字中任选一个，但因为不能有重复的，所以要排除第一次选择的，第二次选择的时候只能从剩下的8个数字中选一个…… 。这个选择的过程就比较明朗了，我们可以把它看做一棵9叉树，除叶子结点外每个节点都有9个子节点，也就是下面这样

文章插图

从9个数字中任选一个，就是沿着他的任一个分支一直走下去，其实就是DFS（如果不懂DFS的可以看下373 ，数据结构-6,树），二叉树的DFS代码是下面这样的

public static void treeDFS(TreeNode root) {if (root == null)return;System.out.println(root.val);treeDFS(root.left);treeDFS(root.right);}

这里可以仿照二叉树的DFS来写一下9叉树， 9叉树的DFS就是通过递归遍历他的9个子节点，代码如下

public static void treeDFS(TreeNode root) {//递归必须要有终止条件if (root == null)return;System.out.println(root.val);//通过循环 ， 分别遍历9个子树for (int i = 1; i <= 9; i++) {//2 ， 一些操作 ， 可有可无 ， 视情况而定treeDFS("第i个子节点");//3 ， 一些操作 ， 可有可无 ， 视情况而定}}

DFS其实就相当于遍历他的所有分支，就是列出他所有的可能结果，只要判断结果等于n就是我们要找的，那么这棵9叉树最多有多少层呢，因为有k个数字，所以最多只能有k层。来看下代码

public List<List<Integer>> combinationSum3(int k, int n) {List<List<Integer>> res = new ArrayList<>();dfs(res, new ArrayList<>(), k, 1, n);return res;}private void dfs(List<List<Integer>> res, List<Integer> list, int k, int start, int n) {//终止条件 ， 如果满足这个条件 ， 再往下找也没什么意义了if (list.size() == k || n <= 0) {//如果找到一组合适的就把他加入到集合list中if (list.size() == k && n == 0)res.add(new ArrayList<>(list));return;}//通过循环 ， 分别遍历9个子树for (int i = start; i <= 9; i++) {//选择当前值list.add(i);//递归dfs(res, list, k, i + 1, n - i);//撤销选择list.remove(list.size() - 1);}}

代码相对来说还是比较简单的，我们来分析下（如果看懂了可以直接跳过）。
1 ，代码dfs中最开始的地方是终止条件的判断，之前在426 ，什么是递归，通过这篇文章，让你彻底搞懂递归中讲过，递归必须要有终止条件。
2 ，下面的for循环分别遍历他的9个子节点，注意这里的i是从start开始的，所以有可能还没有9个子树，前面说过，如果从9个数字中选择一个之后，第2次就只能从剩下的8个选择了，第3次就只能从剩下的7个中选择了……