什么是回溯算法？组合问题理解回溯

什么是回溯算法？组合问题理解回溯

回溯算法 与 深度优先遍历对比

• 什么叫回溯算法
• 组合总和
• • 解释
• 总结

来源：公众号（数据结构和算法）

什么叫回溯算法

对于回溯算法的定义是这样描述的：

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法。

回溯算法其实就是一个不断探索尝试的过程，探索成功了也就成功了，探索失败了就在退一步，继续尝试……，

组合总和

找出所有相加之和为 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代码是下面这样的

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);//撤销选择ve(list.size() - 1);}
}

• 1，代码dfs中最开始的地方是终止条件的判断，递归必须要有终止条件。

• 2，下面的for循环分别遍历他的 9 个子节点，注意这里的i是从start开始的，所以有可能还没有9个子树，前面说过，如果从 9 个数字中选择一个之后，第2次就只能从剩下的 8 个选择了，第3次就只能从剩下的7个中选择了……

• 3，在第20行dsf中的start是i+1，这里要说一下为什么是i+1。比如我选择了3，下次就应该从4开始选择，如果不加1，下次还从3开始就出现了数字重复，明显与题中的要求不符

• 4，for循环的i为什么不能每次都从1开始，如果每次都从1开始就会出现结果重复，比如选择了[1，2]，下次可能就会选择[2，1]。

• 5，如果对回溯算法不懂的，可能最不容易理解的就是最后一行，为什么要撤销选择。因为会出现分支污染问题，因为list是引用传递，当从一个分支跳到另一个分支的时候，如果不把前一个分支的数据给移除掉，那么list就会把前一个分支的数据带到下一个分支去，造成结果错误。

要搞懂最后一行代码首先要明白什么是递归，递归分为递和归两部分，递就是往下传递，归就是往回走。递归你从什么地方调用最终还会回到什么地方去，我们来画个简单的图看一下

这是一棵非常简单的3叉树，假如要对他进行DFS遍历，当沿着1→2这条路径走下去的时候，list中应该是[1，2]。

因为是递归调用最终还会回到节点1，如果不把2给移除掉，当沿着1→4这个分支走下去的时候就变成[1，2，4]，但实际上1→4这个分支的结果应该是[1，4]，这是因为我们把前一个分支的值给带过来了。

当1，2这两个节点遍历完之后最终还是返回节点1，在回到节点1的时候就应该把节点2的值给移除掉，让list变为[1]，然后再沿着1→4这个分支走下去，结果就是[1，4]。

总结

总结一下回溯算法的代码模板

private void backtrack("原始参数") {//终止条件(递归必须要有终止条件)if ("终止条件") {//一些逻辑操作（可有可无，视情况而定）return;}for (int i = "for循环开始的参数"; i < "for循环结束的参数"; i++) {//一些逻辑操作（可有可无，视情况而定）//做出选择//递归backtrack("新的参数");//一些逻辑操作（可有可无，视情况而定）//撤销选择}
}