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

小灰灰 2022-11-18 13:57 280阅读 0赞

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

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

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

# 什么叫回溯算法 #

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

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

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

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

# 组合总和 #

找出所有相加之和为 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个子节点`，也就是下面这样  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70]  
从 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);
            //撤销选择
            list.remove(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`就会把前一个分支的数据带到下一个分支去，造成结果错误。

要搞懂最后一行代码首先要明白什么是递归，递归分为递和归两部分，递就是往下传递，归就是往回走。递归你从什么地方调用最终还会回到什么地方去，我们来画个简单的图看一下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 1]  
这是一棵非常简单的`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("新的参数");
            //一些逻辑操作（可有可无，视情况而定）
    
            //撤销选择
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70]: /images/20221022/9d205a895b5a4440bf2f3a0f61c684e4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70 1]: /images/20221022/209d5e55e2864fc3af0be4f5b983f90c.png