leetcode刷题笔记之回溯算法

前言

这段时间一直在笔试面试的循环中，属实心力憔悴。但是在刷题的过程中也发现了一些自己的不足，比如算法方面的二叉树、动态规划和回溯，这一块为了更好地提升自己，所以想总结一下不断刷题解的心得，作为刷题的笔记之一。

回溯算法本身

回溯算法的核心思想其实比较容易理解，简单来说：排列组合+合理的剪枝，剪去中途就发现不可能的样例然后往回走从而达到降低时间-空间复杂度的目的。举个比较简单的例子，123这三个数字的排列有几个？在看到这个问题的时候我们会先将一个一个元素视为单一定点。然后先拿出1作为第一个元素的时候，考虑第二个元素在2的情况下，那么第三个元素就应该是3，那么这就是一个合理的组合123。如果是2的话122。是一个不合理的排列，我们抛弃掉这个元素，然后继续寻找下一个排列。以上就是一个简单的追踪-剪枝过程。以下面流程图作为一个简单的总结：

1
2
3
4
5
6
7
8
9
10
（2，3同理，这里没有画下去，只是一个简单的流程）
开始
| \ \ 
1  2 3
| \ 
2  3
| \ 
3 2
  |
  (此时2不合理，所以这条枝不会被记录到最终的结果集因而去掉)

在实际的场景中，一般是伴随着复杂的剪枝条件和大量的组合数据进行分析，从而得出回溯时合适的剪枝点，以及需要记录的上下文。总结一下就是，回溯算法比较像是说一个精简的穷举法。

接下来先上一个经典题吧leetcode 46:全排列。

给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:

1
2
3
4
5
6
7
8
9
10
>输入: [1,2,3]
>输出:
>[
 [1,2,3],
 [1,3,2],
 [2,1,3],
 [2,3,1],
 [3,1,2],
 [3,2,1]
>]

对于这道题而言，因为给出的case里面是没有重复字符的，也就是说我们需要考虑的剪枝条件就是每个数字是否被用过了第二次，如果用过了，则返回上一层试下一个数字。在当前状态机也就是暂存排列情况的队列达到case的长度的时候，视为一个通过情况，并且将其加入结果集。当全部枝被遍历完之后，即得到所有情况的时候，则是得到了想要的排列情况集。用伪代码描述来看就是(灵感来自于 扒一扒回溯算法的裤子 via labuladong)：

1
2
3
4
5
6
7
8
for 字符 in 字符列表:
    # 选择字符
    将该字符从字符列表移除
    路径.add(字符)
    backtrack(路径, 当前字符列表)
    # 撤销选择
    路径.remove(选择)
    将该选择再加入字符列表

对于backtrack函数而言：

1
2
3
4
5
6
7
8
if 路径长度==case长度:
    result.add(路径)
    return

for 字符 in 当前字符列表:
    做选择
    backtrack(路径, 当前字符列表)
    撤销选择

两段伪代码下来，全排列的框架基本上就搭建完成了。然后是完整代码，这个时候其实只需要基于上面的伪代码进行些许修改：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Main{
  List<List<Integer>> res = new LinkedList<>();

  /* 主函数，输入一组不重复的数字，返回它们的全排列 */
  List<List<Integer>> permute(int[] nums) {
      // 记录「路径」
      LinkedList<Integer> track = new LinkedList<>();
      backtrack(nums, track);
      return res;
  }

  // 路径：记录在 track 中
  // 选择列表：nums 中不存在于 track 的那些元素
  // 结束条件：nums 中的元素全都在 track 中出现
  void backtrack(int[] nums, LinkedList<Integer> track) {
      // 触发结束条件
      if (track.size() == nums.length) {
          res.add(new LinkedList(track));
          return;
      }
      
      for (int i = 0; i < nums.length; i++) {
          // 排除不合法的选择
          if (track.contains(nums[i]))
              continue;
          // 做选择
          track.add(nums[i]);
          // 进入下一层决策树
          backtrack(nums, track);
          // 取消选择
          track.removeLast();
      }
  }
}

其实整体比较简单，因为这里设计的剪枝条件和数据量都不是很大。接下来看一下稍微复杂一点的leetcode 47:全排列2

给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:

1
2
3
4
5
6
7
>输入: [1,1,2]
>输出:
>[
 [1,1,2],
 [1,2,1],
 [2,1,1]
>]

对于这道题而言，比较麻烦的是剪枝的时候需要考虑到某个字符是否被用过，如果被用过的话，是第几次被用过，从而不进行重复的追溯。即剪枝代码是：
(from 回溯搜索 + 剪枝 via liweiwei1419)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
if (depth == len) {
    res.add(new ArrayList<>(path));
    return;
}

for (int i = 0; i < len; ++i) {
    if (used[i]) {
        continue;
    }

    // 剪枝条件：i > 0 是为了保证 nums[i - 1] 有意义
    // 写 !used[i - 1] 是因为 nums[i - 1] 在深度优先遍历的过程中刚刚被撤销选择
    if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
        continue;
    }

    path.addLast(nums[i]);
    used[i] = true;

    dfs(nums, len, depth + 1, used, path, res);
    // 回溯部分的代码，和 dfs 之前的代码是对称的
    used[i] = false;
    path.removeLast();
}

可以从代码里面看到，主要增加的是对于某个字符是否使用过的剪枝。区别就在于主要是添加used[i]来判断字符是否被用过,然后再添加上一个样例中对于长度的剪枝和判断，则生成了对于这个问题的题解。

总结

总而言之，回溯算法的核心思想就是深度遍历+剪枝。但是由于回溯算法的特殊性，尤其要注意回溯时空间复杂度。最后是一些回溯算法经典题目：

17.电话号码的字母组合
39. 组合总和
40. 组合总和 II
51. N皇后
60. 第k个排列
78. 子集
90. 子集 II