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

3 ，在第20行dsf中的start是i+1 ，这里要说一下为什么是i+1 。比如我选择了3 ，下次就应该从4开始选择，如果不加1 ，下次还从3开始就出现了数字重复，明显与题中的要求不符
4 ， for循环的i为什么不能每次都从1开始，如果每次都从1开始就会出现结果重复，比如选择了[1 ， 2] ，下次可能就会选择[2 ， 1] 。
5 ，如果对回溯算法不懂的，可能最不容易理解的就是最后一行，为什么要撤销选择。如果经常看我公众号的同学可能知道，也就是我经常提到的分支污染问题，因为list是引用传递，当从一个分支跳到另一个分支的时候，如果不把前一个分支的数据给移除掉，那么list就会把前一个分支的数据带到下一个分支去，造成结果错误（下面会讲）。那么除了把前一个分支的数据给移除以外还有一种方式就是每个分支都创建一个list ，这样每个分支都是一个新的list ，都不互相干扰，也就是下面图中这样

文章插图

代码如下

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 ， 和原来的list撇清关系 ， 对当前list的修改并不会影响到之前的listList<Integer> subList = new LinkedList<>(list);subList.add(i);//递归dfs(res, subList, k, i + 1, n - i);//注意这里没有撤销的操作 ， 因为是在一个新的list中的修改 ， 原来的list并没有修改 ， //所以不需要撤销操作}}

我们看到最后并没有撤销的操作，这是因为每个分支都是一个新的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("新的参数");//一些逻辑操作（可有可无 ， 视情况而定）//撤销选择}}

有了模板，回溯算法的代码就非常容易写了，下面就根据模板来写几个经典回溯案例的答案。
八皇后问题八皇后问题也是一道非常经典的回溯算法题，前面也有对八皇后问题的专门介绍，有不明白的可以先看下394 ，经典的八皇后问题和N皇后问题。他就是不断的尝试，如果当前位置能放皇后就放，一直到最后一行如果也能放就表示成功了，如果某一个位置不能放，就回到上一步重新尝试。比如我们先在第1行第1列放一个皇后，如下图所示