LeetCode 回溯

递归对于算法萌新宝宝们已经很难了，回溯是递归的升级版，恐怕更是难倒不少英雄汉。这篇就总结一下 LeetCode 上常见的回溯题目，这些鬼问题单独看一个都不算难，全部做一遍之后大概就晕了。

总结

回溯问题通常包含对某一集合的递归遍历，在遍历的过程中选取元素，在回溯的过程中撤销选取。最终达到遍历所有可选取的组合，记录符合条件的那些。

排列与组合

递归遍历的过程中，每次都从第一个元素开始，还是从上一层遍历的位置开始呢？对于排列问题，每次都要从头开始；对于组合问题，需要接续遍历，因此递归函数需要一个参数指明从哪开始遍历。

• 排列：选中集合的不同顺序视为多个有效答案。
• 组合：选中集合的不同顺序只视为一个有效答案。

需要强调的是，题目要求答案有固定的顺序，不代表就是排列问题。这里我们只看每一个选中元素的集合，其不同排列有几个是有效的。如果只有一个有效，那么就是组合问题。

• 排列问题：需要全量遍历，即每一层递归都要从头开始遍历每一个元素。 需要 used 数组或其他方式记录已选取的元素。

• 组合问题：需要接续遍历，即每一层递归从上一层的位置开始继续遍历元素。 至于要不要从下一个开始，取决于题目是否允许多次选取同一个元素。

去重

排列或组合的回溯问题通常要求答案去重。

排序跳过去重

在原集合允许排序的情况下，排序跳过是简单高效的去重方案。

对于接续遍历，遇到两个连续的相同元素时跳过即可。需要注意的是只能向前去重，代码如下：

if (i > 0 && nums[i] == nums[i - 1]) continue;

如果向后则会漏解。例如计算集合 {1,2,2} 的组合，只能得到 {1,2} 而漏掉 {1,2,2}。

对于全量遍历，需要与 used 标记配合一起去重。代码如下：

if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;

!used[i - 1] 的作用是把去重范围限制在同一层递归中。只要任意数字在每一位最多只出现一次，答案就不会有重复。而第 N 层递归正是决定这组答案的第 N 位是什么数字。

例如求集合 {1,1,2} 的排列，若不加这个额外条件则会漏掉 {1,1,2} 或 {2,1,1} 这样的解，此时的实际语义是「任意数字在任意位置最多只出现一次」。

哈希表去重

有时不允许对原集合进行排序，那么就得用哈希表。

哈希表记录元素的值还是下标？那要看题目要求，如果值重复就算答案重复，自然要记录值。如果选取多个相等的元素不算重复，那么就记录下标。

最后，每层递归都该有自己的哈希表。理由和刚才一样，独立哈希表实现的是「任意数字在每一位最多只出现一次」，这也是题目去重的含义。而全局哈希表实现的是「任意数字在任意位置最多只出现一次」。

37 需要提前结束的回溯

传送门

这题是解数独，是个经典的回溯问题。虽然标记为 hard 但知道思想后不难。

这题的特点是只有一个解，因此找到一个解后应该立即返回来节约时间。需要注意的是递归不是循环，光一次返回不行，所有递归调用的地方都必须对递归返回值进行判断，如果已经找到解则立即结束当前递归。

数独的递归体现在每一个格子都需要尝试填入每一个数字，回溯体现在如果填入某数字导致后续无解，就要按层依次撤销。

答案如下：

class Solution {
  public void solveSudoku(char[][] board) {
    backtracking(board, 0, 0);
  }

  private boolean backtracking(char[][] board, int row, int col) {
    if (row == 9) return true; // 已填完所有格子
    int nextRow = col == 8 ? row + 1 : row;
    int nextCol = col == 8 ? 0 : col + 1;
    if (board[row][col] != '.')
      return backtracking(board, nextRow, nextCol); // 不能修改题目填好的数字
    for (char ch = '1'; ch <= '9'; ch++) {
      if (!valid(board, row, col, ch)) continue;
      board[row][col] = ch;
      if (backtracking(board, nextRow, nextCol))
        return true; // 找到一个答案，结束当前递归
      board[row][col] = '.'; // 无解，撤销更改
    }
    return false; // 尝试了所有值都不行，无解
  }

  private boolean valid(char[][] board, int row, int col, char val) {
    for (int i = 0; i < 9; i++) {
      if (board[i][col] == val) return false;
      if (board[row][i] == val) return false;
    }
    int startRow = row / 3 * 3, startCol = col / 3 * 3;
    for (int r = startRow; r < startRow + 3; r++)
      for (int c = startCol; c < startCol + 3; c++)
        if (board[r][c] == val) return false;
    return true;
  }
}

17 组合问题

传送门

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

...

首先来分析是排列还是组合。

这道题的本质是：给一串数字，每个数字可以对应多个字符，我们要分别选取它们组成字符串。例如 2-a/b/c, 3-d/e/f，给定数字序列 23，答案有 9 个集合（集合是无需的）：{ad},{ae},{af},{bd},{be},{bf},{cd},{ce},{cf}，那么对于每个集合，其多个顺序的排列有几个是有效答案？例如第一个集合有两个排列：<ad>,<da>，显然只有 <ad> 有效。因此这是组合问题。

java 答案：

class Solution {
  private final char[][] board = {
    {'a', 'b', 'c'}, {'d', 'e', 'f'}, {'g', 'h', 'i'}, {'j', 'k', 'l'},
    {'m', 'n', 'o'}, {'p', 'q', 'r', 's'}, {'t', 'u', 'v'}, {'w', 'x', 'y', 'z'},
  };
  LinkedList<String> result = new LinkedList<>();

  public List<String> letterCombinations(String digits) {
    int[] ds = new int[digits.length()];
    for (int i = 0; i < ds.length; i++)
      ds[i] = digits.charAt(i) - '0';
    backtracking(ds, 0, new StringBuilder(digits.length()));
    return result;
  }

  private void backtracking(int[] digits, int index, StringBuilder sb) {
    if (index == digits.length) { // 根据题目要求定义的结束条件（遍历完所有数字）
      if (sb.length() > 0) result.add(sb.toString());
      return;
    }
    for (char ch : board[digits[index] - 2]) {
      sb.append(ch);
      backtracking(digits, index + 1, sb);
      sb.setLength(sb.length() - 1);
    }
  }
}

39 可重复的组合问题

传送门

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times.

这是组合问题吗？

例如给定 candidates = [2,3], target = 7，则 {2,2,3} 是一个解集合，其多个排列 <2,2,3>, <2,3,2>, ... 视为重复，因此只有一个有效解。所以是组合问题。

按照总结，组合问题需要「接续遍历」，也就是从上层递归遍历到的位置开始。但这题规定数字可以多次使用，所以具体来讲，得严格从上层的位置再次遍历，而不是从它的下一个元素开始。

[小优化1]

本题限制 candidates[x] > 0 && target > 0，因此若中间某一步发现和已经超过 target 就不用继续递归了。

[小优化2]

进一步，可以把 candidates 排序一下，若中间某一步的和超过 target，不仅不用继续递归，当前循环也可以退出了（因为后边的数更大，其和一定超过 target）

491 不允许排序的去重

传送门

Given an integer array nums, return all the different possible non-decreasing subsequences of the given array with at least two elements. You may return the answer in any order.

---

解释一下题目，虽然写的是「subsequences」，但实际上不要求连续。例如对于数组 nums = [4,6,7,7],[4,7] 也是一个有效答案。

按照前几个总结，先提取一下这题目的关键要求：

• 子序列：答案的每一项只有一个有效顺序，即多个顺序只算作一个答案，因此这是组合题，递归函数要有起始下标参数。
• 答案要去重：考虑排序跳过法或哈希表法

关于这是组合题还是排序题可能有同学有疑问。再说一遍「组合」并不代表顺序不重要，而是说相同的几个元素不同的排列只有一个有效答案。传统的组合中，不同的排列视为重复，因此只有一个有效答案。这道题中不同的排列只有一个合法，最终也只有一个有效答案。

接下来是是去重。之前我们通过对给定数组排序，然后比较当前元素与循环的上一个元素来跳过重复。但是这道题不允许进行排序，否则元素的相对位置改变，得出的答案就不再是「子序列」了，例如 [4,7] 不是 [7,4,3] 的子序列。但原数组排序后变成 [3,4,7]，那么 [4,7] 就成了有效答案。

所以这题必须用哈希表来去重。接下来的问题是用值去重还是下标去重？显然用值。因为 [4,6,7], [4,6,7] 这两个子序列即使用的是不同的 7，也算作重复答案。

答案如下：

class Solution {
  LinkedList<List<Integer>> result = new LinkedList<>();

  public List<List<Integer>> findSubsequences(int[] nums) {
    backtracking(nums, 0, new LinkedList<>());
    return result;
  }

  private void backtracking(int[] nums, int start, LinkedList<Integer> sub) {
    if (sub.size() >= 2) { // 题目要求至少有两个元素
      result.add(new ArrayList<>(sub));
    }
    HashSet<Integer> used = new HashSet<>();
    for (int i = start; i < nums.length; i++) {
      // 去重
      if (used.contains(nums[i])) continue;
      // 确保答案是非递减序列
      if (!sub.isEmpty() && nums[i] < sub.getLast()) continue;
      sub.add(nums[i]);
      used.add(nums[i]);
      backtracking(nums, i + 1, sub);
      sub.removeLast();
    }
  }
}