回溯法套路总结与应用

概述

回溯法常用于遍历一个列表元素的所有所有子集，比如全排列问题。可以说深度优先搜索就是回溯法的一种特殊形式。该方法的时间复杂度比较大一般为 O(N!)，它不像动态规划存在重叠子问题可以优化，当然在某些情况下，我们可以通过剪枝来进行优化，当然这个技巧性可能较高。本篇文章主要从回溯法的基本思想入手，总结出一套模板，灵活运用模板便可以讲解大部分回溯算法的问题。

模板与算法

回溯法 其实核心思想就是以深度优先进行暴力穷举，最重要的是做到补充不漏，整个过程跟 决策树 的遍历是类似的。其通用的一个算法模板如下：

 result = []
 def backtrack(路径, 选择列表):
     if 满足结束条件:
         result.add(路径)
         return
 
     for 选择 in 选择列表:
         做选择
         backtrack(路径, 选择列表)
         撤销选择

从这个模板中，我们可以看出，要用好回溯算法其实重点就是解决三个问题：

1. 路径：也就是已经做出的选择
2. 选择列表
3. 结束条件

下边我们通过一个全排列问题来展开说明：

全排列问题

具体题目如下:

问题本身很简单，我们高中的时候可能就会通过画决策树来解决整个问题：

为啥说这是决策树呢，因为你在每个节点上其实都在做决策。比如说你站在下图的红色节点上：

你现在就在做决策，可以选择 1 那条树枝，也可以选择 3 那条树枝。为啥只能在 1 和 3 之中选择呢？因为 2 这个树枝在你身后，这个选择你之前做过了，而全排列是不允许重复使用数字的。

通过前边的说明，针对该问题需要解决的三个问题分别为：

1. 路径：[2]就是路径，记录已经做过的选择
2. 选择列表：[1,3]就是选择列表，表示接下来可进行选择元素的列表
3. 结束条件：便利到树的底层，也就是说选择列表为空的时候结束

进而套用上边的模板，我们可以得出如下代码：

   List<List<Integer>> result = new ArrayList<>();
 
     /**
      * 使用回溯法，解决全排列问题
      * @param nums
      * @return
      */
     public List<List<Integer>> permute(int[] nums) {
         LinkedList<Integer> track = new LinkedList<>();
         backtrace(nums, track);
         return result;
     }
 
     private void backtrace(int[] nums, LinkedList<Integer> track) {
         // add track
         if (track.size() == nums.length) {
             result.add(new LinkedList<>(track));
         }
         for (int num : nums) {
             if (track.contains(num)) {
                 continue;
             }
             // make choice
             track.add(num);
             // recursive
             backtrace(nums, track);
             // backtrace choince
             track.removeLast();
         }
     }

应用

同样的再做一道题目练习一下：

该问题，较之上一个问题，最大的不同就是会有重复的元素，因此会增加重复元素的判断，但整体难度也不大，套用模板可以得出如下解决方案：

 List<List<Integer>> result = new ArrayList<>();
   byte[] visited = new byte[22];
 
   public List<List<Integer>> permuteUnique(int[] nums) {
     LinkedList<Integer> track = new LinkedList<>();
     Arrays.sort(nums);
     backtrace(nums, track);
     return result;
   }
 
   private void backtrace(int[] nums, LinkedList<Integer> track) {
     // 倡导到达nums.lenghth则记录路径
     if (nums.length == track.size()) {
       result.add(new LinkedList<>(track));
     }
     for (int i = 0; i < nums.length; i++) {
       //已经添加过的元素直接跳过
       if (visited[i] == 1) {
         continue;
       }
       //与上一个元素相同，且没有添加过直接跳过
       if (i != 0 && nums[i] == nums[i - 1] && visited[i - 1] == 0) {
         continue;
       }
       visited[i] = 1;
       track.add(nums[i]);
       backtrace(nums, track);
       track.removeLast();
       visited[i] = 0;
     }
   }

总结

回溯算法就是个多叉树的遍历问题，关键就是在前序遍历和后序遍历的位置做一些操作，算法框架如下：

 result = []
 def backtrack(路径, 选择列表):
     if 满足结束条件:
         result.add(路径)
         return
 
     for 选择 in 选择列表:
         做选择
         backtrack(路径, 选择列表)
         撤销选择

写 backtrack 函数时，需要维护走过的「路径」和当前可以做的「选择列表」，当触发「结束条件」时，将「路径」记入结果集。

只要确定了选择的条件，以及记录路径的调整，整个代码很容易便可以实现出来了。

参考

1. https://labuladong.gitbook.io/algo/di-ling-zhang-bi-du-xi-lie/hui-su-suan-fa-xiang-jie-xiu-ding-ban#san-zui-hou-zong-jie
2. https://greyireland.gitbook.io/algorithm-pattern/suan-fa-si-wei/backtrack#permutations