回溯算法解题框架

Table of Contents

一、回溯算法一般概念

1. 回溯算法定义

维基百科

回溯法是暴力搜索法中的一种。

回溯法 采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：

1. 找到一个可能存在的正确答案
2. 在尝试了所有可能的分步方法后宣告该问题没有答案

2. 与DFS 的区别

DFS 定义：

深度优先搜索 算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。这个算法会 尽可能深 的搜索树的分支。当结点 v 的所在边都己被探寻过，搜索将 回溯 到发现结点 v 的那条边的起始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择其中一个作为源结点并重复以上过程，整个进程反复进行直到所有结点都被访问为止。

在网上经常会看到把回溯算法和 DFS 视为一致，但两者从定义上还是有一些不同。回溯算法强调回溯的思想，如果遇到不合条件的路就会进行回溯，不再继续向下搜索。而DFS 强调遍历的过程，每一个树中的节点都要遍历到，与BFS 形成对比。回溯过程按照深度优先搜索的策略，从根节点出发深度搜索解空间树。（其实回溯法就是对隐式图的深度优先搜索，解决一个回溯问题，实际上就是一个决策树的遍历过程）

所以可以说 Backtracking（回溯）属于 DFS。

• 普通 DFS 主要用在 可达性问题 ，这种问题只需要执行到特点的位置然后返回即可。
• 而 Backtracking 主要用于求解 排列组合 问题，例如有 { ‘a’,‘b’,‘c’ } 三个字符，求解所有由这三个字符排列得到的字符串，这种问题在执行到特定的位置返回之后还会继续执行求解过程。

因为 Backtracking 不是立即返回，而要继续求解，因此在程序实现时，需要注意对元素的标记问题：

• 在访问一个新元素进入新的递归调用时，需要将新元素标记为已经访问，这样才能在继续递归调用时不用重复访问该元素；
• 但是在递归返回时，需要将元素标记为未访问，因为只需要保证在一个递归链中不同时访问一个元素，可以访问已经访问过但是不在当前递归链中的元素。

与穷举的联系

五大算法之一回溯

回溯法简单来说就是按照深度优先的顺序，穷举所有可能性的算法，但是回溯算法比暴力穷举法更高明的地方就是回溯算法可以随时判断当前状态是否符合问题的条件。

一旦不符合条件，那么就退回到上一个状态，省去了继续往下探索的时间。

二、一般步骤与解法

理解决策树的三个基本概念：

1. 路径：也就是已经做出的选择
2. 选择列表：也就是你当前可以做的选择
3. 结束条件：也就是到达决策树底层，无法再做选择的条件

选自算法小抄，细节参考这里

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

现在可以解答开头的几个名词：[2] 就是「路径」，记录你已经做过的选择；[1,3] 就是「选择列表」，表示你当前可以做出的选择；「结束条件」就是遍历到树的底层，在这里就是选择列表为空的时候。

如果明白了这几个名词，可以把「路径」和「选择」列表作为决策树上每个节点的属性

一般解法：

1、针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解。

2、确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间 。

3、以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。

三、框架

1. 回溯框架

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

回溯算法不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高。

2. DFS 框架

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件: //(可选)
        result.add(路径)
        return
            
    遍历到一个节点
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)

差别也可以看图遍历，我也是写完后才发现这个有介绍两者的区别，看了一遍后发现很有启发。

四、例题

1. DFS

• 查找最大的连通面积

  695. 岛屿的最大面积

  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 35 36

  class Solution { private int area = 0; private int count; private int sizeRow; private int sizeCol; public int maxAreaOfIsland(int[][] grid) { if (grid == null || grid.length == 0) return 0; int m = grid.length; int n = grid[0].length; this.sizeRow = m; this.sizeCol = n; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 1) { count = 0; dfs(grid, i, j); } } } return area; } private void dfs(int[][] grid, int row, int col) { if (row < 0 || col < 0 || row >= sizeRow || col >= sizeCol || grid[row][col] == 0) return; count++; grid[row][col] = 0; dfs(grid, row, col - 1); dfs(grid, row, col + 1); dfs(grid, row - 1, col); dfs(grid, row + 1, col); area = Math.max(area, count); } }

• 矩阵中的连通分量数目

  200. 岛屿数量

  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

  class Solution { private int count = 0; private int m, n; public int numIslands(char[][] grid) { if (grid == null || grid.length == 0) return 0; m = grid.length; n = grid[0].length; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == '1') { count++; dfs(grid, i, j); } } } return count; } private void dfs(char[][] grid, int row, int col) { if (row < 0 || row >= m || col < 0 || col >= n || grid[row][col] == '0') return; grid[row][col] = '0'; dfs(grid, row, col - 1); dfs(grid, row, col + 1); dfs(grid, row - 1, col); dfs(grid, row + 1, col); } }

2. 回溯

• 集合划分

  698. 划分为k个相等的子集

  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

  class Solution { public boolean canPartitionKSubsets(int[] nums, int k) { if (k > nums.length) return false; int sum = 0; for (int v : nums) sum += v; if (sum % k != 0) return false; int[] sums = new int[k]; return backtracking(nums, 0, sums, sum / k); } private boolean backtracking(int[] nums, int index, int[] sums, int target) { if (index < nums.length) { for (int i = 0; i < sums.length; i++) { if (sums[i] >= target) { continue; } sums[i] += nums[index]; if (backtracking(nums, index+1, sums, target)) { return true; } sums[i] -= nums[index]; } } else { for (int i = 0; i < sums.length; i++) { if (sums[0] != target) return false; } return true; } return false; } }

  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 35 36

  class Solution { public boolean canPartitionKSubsets(int[] nums, int k) { if (k > nums.length) return false; int sum = 0; for (int v : nums) sum += v; if (sum % k != 0) return false; boolean[] used = new boolean[nums.length]; int target = sum / k; // k 号桶初始什么都没装，从 nums[0] 开始做选择 return backtracking(k, 0, nums, 0, used, target); } public boolean backtracking(int k, int sum, int[] nums, int index, boolean[] used, int target) { if (k == 0) return true; if (sum == target) { return backtracking(k-1, 0, nums, 0, used, target); } for (int i = index; i < nums.length; i++) { if (used[i]) continue; if (sum + nums[i] > target) { continue; } sum += nums[i]; used[i] = true; if (backtracking(k, sum, nums, i+1, used, target)) return true; used[i] = false; sum -= nums[i]; } return false; } }

  有些题也可以用DFS 但不是最优解法

  419. 甲板上的战舰

• 子集

  78. 子集

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

  class Solution { List<List<Integer>> res = new ArrayList<>(); public List<List<Integer>> subsets(int[] nums) { LinkedList<Integer> list = new LinkedList<>(); backtracking(nums, 0, list); return res; } private void backtracking(int[] nums, int start, LinkedList<Integer> list) { res.add(new LinkedList(list)); for (int i = start; i < nums.length; i++) { list.addLast(nums[i]); backtracking(nums, i+1, list); list.removeLast(); } } }

• 组合

  77. 组合

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

  class Solution { List<List<Integer>> res = new ArrayList<>(); public List<List<Integer>> combine(int n, int k) { LinkedList<Integer> list = new LinkedList<>(); backtracking(n, k, 1, list); return res; } private void backtracking(int n, int k, int num, LinkedList<Integer> list) { if (k == list.size()) { res.add(new ArrayList<>(list)); return; } while (num + k - list.size() - 1<= n) { list.addLast(num++); backtracking(n, k, num, list); list.removeLast(); } } }

• 排列

  46. 全排列

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

  class Solution { List<List<Integer>> res = new ArrayList<>(); public List<List<Integer>> permute(int[] nums) { LinkedList<Integer> list = new LinkedList<>(); backtracking(nums, 0, list); return res; } private void backtracking(int[] nums, int size, LinkedList<Integer> list) { if (size == nums.length) { res.add(new LinkedList<>(list)); return; } for (int i = 0; i < nums.length; i++) { if (list.contains(nums[i])) { continue; } list.addLast(nums[i]); backtracking(nums, size+1, list); list.removeLast(); } } }