回溯算法Tag

回溯三部曲：
回溯函数模板返回值以及参数
回溯函数终止条件
回溯搜索的遍历过程

回溯算法

理论基础

回溯法也可以叫做回溯搜索法，它是一种搜索的方式。
回溯是递归的副产品，只要有递归就会有回溯。所以以下讲解中，回溯函数也就是递归函数，指的都是一个函数。
回溯法，一般可以解决如下几种问题：
- 组合问题：N 个数里面按一定规则找出 k 个数的集合
- 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个 N 个数的集合里有多少符合条件的子集
- 排列问题：N 个数按一定规则全排列，有几种排列方式
- 棋盘问题：N 皇后，解数独等等
回溯法解决的问题都可以抽象为树形结构，因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。

★回溯三部曲

回溯三部曲：

回溯函数模板返回值以及参数：
- 在回溯算法中，我的习惯是函数起名字为 backtracking，这个起名大家随意。
  回溯算法中函数返回值一般为void。
  再来看一下参数，因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。回溯函数伪代码如下：
1
void backtracking(参数)
回溯函数终止条件：
- 什么时候达到了终止条件，树中就可以看出，一般来说搜到叶子结点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。所以回溯函数终止条件伪代码如下：
1
2
3
4
if (终止条件) {
存放结果;
return;
}
回溯搜索的遍历过程：
- 在上面我们提到了，回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。如图：
  回溯函数遍历过程伪代码如下：
  1
  2
  3
  4
  5
  for (选择：本层集合中元素（树中结点孩子的数量就是集合的大小）) {
  处理结点;
  backtracking(路径，选择列表); // 递归
  回溯，撤销处理结果
  }
  - for 循环就是遍历集合区间，可以理解一个结点有多少个孩子，这个 for 循环就执行多少次。
  - backtracking 这里自己调用自己，实现递归。
  - 大家可以从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子结点就是找的其中一个结果了。

分析完过程，回溯算法模板框架如下：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中结点孩子的数量就是集合的大小）) {
        处理结点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

这份模板很重要，后面做回溯法的题目都靠它了！

1.组合问题

题目

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：
1
2
3
4
5
6
7
8
9
10
输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
示例 2：
1
2
输入：n = 1, k = 1
输出：[[1]]
提示：
- 1 <= n <= 20
- 1 <= k <= n

思路

本题是回溯法的经典题目。直接的解法当然是使用 for 循环，例如示例中 k 为 2，很容易想到用两个 for 循环，这样就可以输出和示例中一样的结果。输入：n = 100, k = 3 那么就三层 for 循环。
如果n为100，k为50呢，那就50层for循环，是不是开始窒息。此时就会发现虽然想暴力搜索，但是用 for 循环嵌套连暴力都写不出来！
回溯搜索法来了，虽然回溯法也是暴力，但至少能写出来，不像 for 循环嵌套 k 层让人绝望。
那么回溯法怎么暴力搜呢？
- 上面我们说了要解决 n 为 100，k 为 50 的情况，暴力写法需要嵌套 50 层 for 循环，那么回溯法就用递归来解决嵌套层数的问题。用递归来做层叠嵌套（可以理解是开 k 层 for 循环），每一次的递归中嵌套一个 for 循环，那么递归就可以用于解决多层嵌套循环的问题了。
把组合问题抽象为如下树形结构：
- 可以看出这棵树，一开始集合是 1，2，3，4，从左向右取数，取过的数，不再重复取。第一次取1，集合变为2，3，4 ，因为k为2，我们只需要再取一个数就可以了，分别取2，3，4，得到集合[1,2] [1,3] [1,4]，以此类推。
- 每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围。
  - 图中可以发现 n 相当于树的宽度，k 相当于树的深度。
- 那么如何在这个树上遍历，然后收集到我们要的结果集呢？
  - 图中每次搜索到了叶子结点，我们就找到了一个结果。相当于只需要把达到叶子结点的结果收集起来，就可以求得 n 个数中 k 个数的组合集合。

回溯法三部曲：

递归函数的返回值以及参数
- 函数里一定有两个参数，既然是集合 n 里面取 k 个数，那么 n 和 k 是两个 int 型的参数。
- 然后还需要一个参数，为 int 型变量 startIndex，这个参数用来记录本层递归的中，集合从哪里开始遍历（集合就是[1,…,n] ）。
  - 为什么要有这个 startIndex 呢？
    startIndex 就是防止出现重复的组合。
1
2
3
List<List<Integer>> result; // 存放符合条件结果的集合
List<Integer> path; // 用来存放符合条件单一结果
void backtracking(int n, int k, int startIndex);
回溯函数终止条件
- 什么时候到达所谓的叶子结点了呢？
  - path 这个数组的大小如果达到 k，说明我们找到了一个子集大小为 k 的组合了，path 存的就是根结点到叶子结点的路径。
1
2
3
4
if (path.size() == k) {
result.add(path);
return;
}

单层搜索的过程

回溯法的搜索过程就是一个树型结构的遍历过程，在如下图中，可以看出 for 循环用来横向遍历，递归的过程是纵向遍历。
如此我们才遍历完图中的这棵树。
- for 循环每次从 startIndex 开始遍历，然后用 path 保存取到的结点 i。

for (int i = startIndex; i <= n; i++) { // 控制树的横向遍历
    path.add(i); // 处理结点
    backtracking(n, k, i + 1); // 递归：控制树的纵向遍历，注意下一层搜索要从i+1开始
    path.remove(Integer.valueOf(i)); // 回溯，撤销处理的结点
}

可以看出 backtracking（递归函数）通过不断调用自己一直往深处遍历，总会遇到叶子结点，遇到了叶子结点就要返回。
backtracking 的下面部分就是回溯的操作了，撤销本次处理的结果。

class Solution {
    private List<List<Integer>> result = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        backTracking(n, k, 1);
        return result;
    }

    public void backTracking(int n, int k, int startIndex) {
        if (path.size() == k) {
            result.add(new ArrayList<>(path));
            return;
        }
        // startIndex用于标识从哪里开始迭代，避免元素重复
        for (int i = startIndex; i <= n; i++) {
            path.add(i);
            backTracking(n, k, i + 1);
            path.remove(path.size() - 1); // 回溯
        }
    }
}

上面的代码耗时很长，所以用剪枝对其进行优化，怎么优化呢？

来举一个例子，n = 4，k = 4 的话，那么第一层 for 循环的时候，从元素 2 开始的遍历都没有意义了。在第二层 for 循环，从元素 3 开始的遍历都没有意义了。
这么说有点抽象，如图所示：
- 可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。
- 如果 for 循环选择的起始位置之后的元素个数已经不足我们需要的元素个数了，那么就没有必要搜索了。

class Solution {
    private List<List<Integer>> result = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        backTracking(n, k, 1);
        return result;
    }

    public void backTracking(int n, int k, int startIndex) {
        if (path.size() == k) {
            result.add(new ArrayList<>(path));
            return;
        }
        // n - startIndex + 1是剩余的还可以被添加到路径中的元素个数
        // k - path.size()是还需要被添加到路径中的元素个数
        if ((n - startIndex + 1) < (k - path.size())) {
            return;
        }
        // startIndex用于标识从哪里开始迭代，避免元素重复
        for (int i = startIndex; i <= n; i++) {
            path.add(i);
            backTracking(n, k, i + 1);
            path.remove(path.size() - 1); // 回溯
        }
    }
}

2.组合总和 III

题目

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字 1 到 9
每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

示例 3:

输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。

提示:

2 <= k <= 9
1 <= n <= 60

思路

回溯三部曲：

确定递归函数参数及返回值：
- 和组合问题一样，依然需要一维数组 path 来存放符合条件的结果，二维数组 result 来存放结果集。
- 接下来还需要如下参数：
  - targetSum（int）目标和，也就是题目中的n。
  - k（int）就是题目中要求 k 个数的集合。
  - sum（int）为已经收集的元素的总和，也就是 path 里元素的总和。
  - startIndex（int）为下一层 for 循环搜索的起始位置。
确定终止条件：
- 什么时候终止呢？
  - k 其实就已经限制树的深度，因为就取 k 个元素，树再往下深了没有意义。
  - 所以如果 path.size() 和 k 相等了，就终止。如果此时 path 里收集到的元素和（sum）和 targetSum（就是题目描述的 n）相同了，就用 result 收集当前的结果。
确定单层递归逻辑：
- 处理过程就是 path 收集每次选取的元素，相当于树型结构里的边，sum 来统计 path 里元素的总和。
  代码如下：
  1
  2
  3
  4
  5
  6
  7
  for (int i = startIndex; i <= 9; i++) {
  sum += i;
  path.add(i);
  backtracking(n, k, sum, i + 1);
  path.remove(path.size() - 1);
  sum -= i;
  }
  别忘了处理过程和回溯过程是一一对应的，处理有加，回溯就要有减！

class Solution {
    private List<List<Integer>> res = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        backtracking(n, k, 0, 1);
        return res;
    }

    public void backtracking(int n, int k, int sum, int startIndex) {
        if (path.size() == k) {
            if (sum == n) {
                res.add(new ArrayList<>(path));
            }
            return;
        }
        for (int i = startIndex; i <= 9; i++) {
            sum += i;
            path.add(i);
            backtracking(n, k, sum, i + 1);
            path.remove(path.size() - 1);
            sum -= i;
        }
    }
}

剪枝优化：

已选元素总和如果已经大于 n 了，那么往后遍历就没有意义了，直接剪掉。

class Solution {
    private List<List<Integer>> res = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        backtracking(n, k, 0, 1);
        return res;
    }

    public void backtracking(int n, int k, int sum, int startIndex) {
        if (path.size() == k) {
            if (sum == n) {
                res.add(new ArrayList<>(path));
            }
            return;
        }
        // 剪枝
        if (sum > n) {
            return;
        }
        for (int i = startIndex; i <= 9; i++) {
            sum += i;
            path.add(i);
            backtracking(n, k, sum, i + 1);
            path.remove(path.size() - 1);
            sum -= i;
        }
    }
}

2.1 组合总和

题目

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

1 2	输入: candidates = [2,3,5], target = 8 输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

1 2	输入: candidates = [2], target = 1 输出: []

提示：

1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates 的所有元素 互不相同
1 <= target <= 40

思路

因为同一个数字可以被重复选取，所以相比于 2.组合总和 III，传入递归函数的不是 i + 1，而是 i。

class Solution {
    private List<List<Integer>> res = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backtracking(candidates, target, 0, 0);
        return res;
    }

    public void backtracking(int[] candidates, int target, int sum, int startIndex) {
        if (sum > target) {
            return;
        }
        if (sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < candidates.length; i++) {
            sum += candidates[i];
            path.add(candidates[i]);
            backtracking(candidates, target, sum, i); // 传入 i 表示可以重复读取当前元素
            path.remove(path.size() - 1); // 回溯
            sum -= candidates[i]; // 回溯
        }
    }
}

2.2 组合总和 II(去重)

题目

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
注意：解集不能包含重复的组合。
示例 1:
1
2
3
4
5
6
7
8
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
示例 2:
1
2
3
4
5
6
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]
提示:
- 1 <= candidates.length <= 100
- 1 <= candidates[i] <= 50
- 1 <= target <= 30

思路

本题的难点在于：集合（数组candidates）有重复元素，但还不能有重复的组合。
- 一些同学可能想了：我把所有组合求出来，再用 set 或者 map 去重，这么做很容易超时！
- 所以要在搜索的过程中就去掉重复组合。
所谓去重，其实就是使用过的元素不能重复选取。
- 都知道组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。没有理解这两个层面上的“使用过” 是造成大家没有彻底理解去重的根本原因。
- 那么问题来了，我们是要同一树层上使用过，还是同一树枝上使用过呢？
  - 回看一下题目，元素在同一个组合内是可以重复的，怎么重复都没事，但两个组合不能相同。
  - 所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。
为了理解去重我们来举一个例子，candidates = [1, 1, 2], target = 3，（方便起见candidates已经排序了）
- 强调一下，树层去重的话，需要对数组排序！
- 选择过程树形结构如图所示：
回溯三部曲：
1. 确定递归函数参数和返回值：
  - 与 39.组合总和 (opens new window) 套路相同，此题还需要加一个 bool 型数组 used，用来记录同一树枝上的元素是否使用过。这个集合去重的重任就是 used 来完成的。
2. 确定递归终止条件：
  - 与 39.组合总和 (opens new window) 相同，终止条件为 sum > target 和 sum == target。
3. 确定单层递归逻辑：
  - 这里与 39.组合总和 (opens new window) 最大的不同就是要去重了。
  - 前面我们提到：要去重的是“同一树层上的使用过”，如何判断同一树层上元素（相同的元素）是否使用过了呢。
    - **如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == false，就说明：前一个树枝，使用了candidates[i - 1]，也就是说同一树层使用过candidates[i - 1]**。此时for循环里就应该做continue的操作。这块比较抽象，如图：
      在图中将 used 的变化用橘黄色标注上，可以看出在 candidates[i] == candidates[i - 1] 相同的情况下：
      - used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
      - used[i - 1] == false，说明同一树层candidates[i - 1]使用过
      为什么 used[i - 1] == false 就是同一树层呢，因为同一树层，used[i - 1] == false 才能表示，当前取的 candidates[i] 是从 candidates[i - 1] 回溯而来的。而 used[i - 1] == true，说明是进入下一层递归，去下一个数，所以是树枝上，如图所示：

class Solution {
    private List<List<Integer>> res = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);  // 首先把candidates排序，让其相同的元素都挨在一起
        boolean[] used = new boolean[candidates.length];
        backtracking(candidates, target, 0, 0, used);
        return res;
    }

    public void backtracking(int[] candidates, int target, int sum, int startIndex, boolean[] used) {
        // for循环中的sum + candidates[i] <= target用于剪枝，来代替
        // if (sum > target) {
        // 	   return;
        // }
        if (sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++) {
            // used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
            // used[i - 1] == false，说明同一树层candidates[i - 1]使用过
            // 要对同一树层使用过的元素进行跳过
            if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
                continue;
            }
            sum += candidates[i];
            path.add(candidates[i]);
            used[i] = true;
            backtracking(candidates, target, sum, i + 1, used);
            path.remove(path.size() - 1); // 回溯
            sum -= candidates[i]; // 回溯
            used[i] = false; // 回溯
        }
    }
}

3.电话号码的字母组合

题目

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
1
2
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
1
2
输入：digits = ""
输出：[]
示例 3：
1
2
输入：digits = "2"
输出：["a","b","c"]
提示：
- 0 <= digits.length <= 4
- digits[i] 是范围 ['2', '9'] 的一个数字。

思路

本题要解决如下三个问题：

数字和字母如何映射
- 可以使用 map 来做映射
两个字母就两个 for 循环，三个字符我就三个 for 循环，以此类推，然后发现代码根本写不出来
- 用回溯来解决 n 个 for 循环的问题。例如：输入：”23”，抽象为树形结构，如图所示：
  - 图中可以看出遍历的深度，就是输入”23”的长度，而叶子节点就是我们要收集的结果，输出[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”]。
  - 写回溯的时候一定要注意横向遍历的是什么，纵向遍历的是什么。
输入 1 * # 按键等等异常情况
- 题目中已经限制了，就不用考虑了，但是正常情况下是要考虑的。

class Solution {
    private String[] strs = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    private List<String> res = new ArrayList<>();
    private StringBuilder sb = new StringBuilder();

    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) { // 排除特殊情况
            return res;
        }
        char[] charArray = digits.toCharArray();
        backtracking(charArray, 0);
        return res;
    }

    public void backtracking(char[] charArray, int cur) {
        // 终止条件
        if (cur == charArray.length) {
            res.add(sb.toString());
            return;
        }
        String s = strs[charArray[cur] - '0'];
        // 单层递归逻辑
        for (int i = 0; i < s.length(); i++) {
            sb.append(s.charAt(i));
            backtracking(charArray, cur + 1);
            sb.deleteCharAt(sb.length() - 1); // 回溯
        }
    }
}

4.分割回文串(切割问题)

题目

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。
示例 1：
1
2
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：
1
2
输入：s = "a"
输出：[["a"]]
提示：
- 1 <= s.length <= 16
- s 仅由小写英文字母组成

思路

本题涉及到两个关键问题：
1. 切割问题，有不同的切割方式
  - 这里的切割，想用for循环暴力解法，可能都不那么容易写出来，所以要换一种暴力的方式，就是回溯。
  - 我们来分析一下切割，其实切割问题类似组合问题。
    例如对于字符串abcdef：
    - 组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中再选取第三个…..。
    - 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段…..。
    所以切割问题，也可以抽象为一棵树形结构，如图：
    递归用来纵向遍历，for循环用来横向遍历，切割线（就是图中的红线）切割到字符串的结尾位置，说明找到了一个切割方法。
    - 递归用于增加切割线，for 循环用于移动切割线的位置。
    此时可以发现，切割问题的回溯搜索的过程和组合问题的回溯搜索的过程是差不多的。
2. 判断回文
  - 判断一个字符串是否是回文。可以使用双指针法，一个指针从前向后，一个指针从后向前，如果前后指针所指向的元素是相等的，就是回文字符串了。

class Solution {
    private List<List<String>> res = new ArrayList<>();
    private List<String> path = new ArrayList<>();
    public List<List<String>> partition(String s) {
        backtracking(s, 0);
        return res;
    }

    // startIndex就是切割线
    public void backtracking(String s, int startIndex) {
        // 找到了一组切割方案
        if (startIndex >= s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            if(isPalindrome(s, startIndex, i)) { // 如果是回文串，就保存
                path.add(s.substring(startIndex, i + 1));
            } else {
                continue;
            }
            backtracking(s, i + 1); // 继续向下切割
            path.remove(path.size() - 1); // 回溯
        }
    }

    // 判断是否是回文串
    public boolean isPalindrome(String s, int left, int right) {
        while (left <= right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

5.复原IP地址

题目

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
- 例如："0.1.2.201" 和"192.168.1.1" 是有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你不能重新排序或删除 s 中的任何数字。你可以按任何顺序返回答案。
示例 1：
1
2
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
示例 2：
1
2
输入：s = "0000"
输出：["0.0.0.0"]
示例 3：
1
2
输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
提示：
- 1 <= s.length <= 20
- s 仅由数字组成

思路

只要意识到这是切割问题，切割问题就可以使用回溯搜索法把所有可能性搜出来，和刚做过的131.分割回文串 (opens new window)就十分类似了。切割问题可以抽象为树型结构，如图：
回溯三部曲：
1. 确定递归函数参数及返回值：
  - 在131.分割回文串 (opens new window)中我们就提到切割问题类似组合问题。
    startIndex 一定是需要的，因为不能重复分割，记录下一层递归分割的起始位置。
    本题我们还需要一个变量 depth，记录已经分段的次数。
2. 确定递归终止条件：
  - 终止条件和131.分割回文串 (opens new window)情况就不同了，本题明确要求只会分成 4 段，所以不能用切割线切到最后作为终止条件，而是分割的段数作为终止条件。
    depth 表示分段数量，depth 为 4 说明字符串分成了 4 段了。
    然后验证一下第四段是否合法，如果合法就加入到结果集里。
3. 确定单层递归逻辑：
  - 在131.分割回文串 (opens new window)中已经讲过在循环遍历中如何截取子串：
    - 在for (int i = startIndex; i < s.length(); i++)循环中 [startIndex, i] 这个区间就是截取的子串，需要判断这个子串是否合法。
      - 如果合法就在字符串后面加上符号.表示已经分割。
      - 如果不合法就结束本层循环，如图中剪掉的分支：

class Solution {
    private List<String> res = new ArrayList<>();
    private StringBuilder sb = new StringBuilder();
    public List<String> restoreIpAddresses(String s) {
        if (s.length() > 12) { // 剪枝
            return res;
        }
        backtracking(s, 0, 0);
        return res;
    }

    public void backtracking(String s, int startIndex, int depth) {
        if (depth == 4) { // 已经分成四段了
            if (startIndex == s.length()) {
                res.add(sb.toString());
            }
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            String temp = s.substring(startIndex, i + 1);
            // 判断是否合法
            if ((temp.length() > 1 && temp.charAt(0) == '0') 
                || temp.length() > 3 
                || Integer.parseInt(temp) > 255) {
                return;
            }
            sb.append(temp);
            if (depth < 3) {
                sb.append(".");
            }
            backtracking(s, i + 1, depth + 1);
            if (depth < 3) {
                sb.delete(sb.length() - (i + 2 - startIndex), sb.length()); // 回溯，要把"."考虑进来
            } else {
                sb.delete(sb.length() - (i + 1 - startIndex), sb.length()); // 回溯
            }
        }
    }
}

6.子集问题

题目

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集不能包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
1
2
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
1
2
输入：nums = [0]
输出：[[],[0]]
提示：
- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
- nums 中的所有元素 互不相同

思路

如果把子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！
以示例中 nums = [1,2,3] 为例把求子集抽象为树型结构，如下：
从图中红线部分，可以看出遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合。
回溯三部曲：
1. 确定递归函数参数及返回值：
  - 子集也是一种组合问题，因为它的集合是无序的，子集 {1,2} 和子集 {2,1} 是一样的。
    那么既然是无序，取过的元素不会重复取，写回溯算法的时候，for 就要从 startIndex 开始，而不是从 0 开始。所以需要传入参数 startIndex。
2. 确定递归终止条件：
  - 从上图可以看出，剩余集合为空的时候，就是叶子节点。那么什么时候剩余集合为空呢？
    - 就是 startIndex 已经大于数组的长度了，就终止了，因为没有元素可取了。
3. 确定单层递归逻辑：
  - 求取子集问题，不需要任何剪枝！因为子集就是要遍历整棵树。

class Solution {
    private List<List<Integer>> res = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        backtracking(nums, 0);
        return res;
    }

    public void backtracking(int[] nums, int startIndex) {
        res.add(new ArrayList<>(path)); // 收集树上的所有节点
        if (startIndex >= nums.length) {
            return;
        }
        for (int i = startIndex; i < nums.length; i++) {
            path.add(nums[i]);
            backtracking(nums, i + 1);
            path.remove(path.size() - 1); // 回溯
        }
    }
}

收集树上所有的节点，那就在进入回溯函数的时候就 add。
收集树中的叶子结点，那就在终止条件满足时才 add。

6.1 子集 II(去重)

题目

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集不能包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
1
2
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：
1
2
输入：nums = [0]
输出：[[],[0]]
提示：
- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10

思路

关于回溯算法中的去重问题，在40.组合总和II (opens new window)中已经详细讲解过了，和本题是一个套路。用示例中的[1, 2, 2] 来举例，如图所示：（注意去重需要先对集合排序）
从图中可以看出，同一树层上重复取 2 就要过滤掉，同一树枝上就可以重复取 2，因为同一树枝上元素的集合才是唯一子集。

class Solution {
    private List<List<Integer>> res = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        boolean[] used = new boolean[nums.length];
        Arrays.sort(nums); // 排序让相同的元素挨在一起
        backtracking(nums, 0, used);
        return res;
    }

    public void backtracking(int[] nums, int startIndex, boolean[] used) {
        res.add(new ArrayList<>(path)); // 保存树上的各个节点
        if (startIndex >= nums.length) {
            return;
        }
        for (int i = startIndex; i < nums.length; i++) {
            if (i > 0 && nums[i - 1] == nums[i] && used[i - 1] == false) {
                continue;
            }
            path.add(nums[i]);
            used[i] = true;
            backtracking(nums, i + 1, used);
            used[i] = false; // 回溯
            path.remove(path.size() - 1); // 回溯
        }
    }
}

7.递增子序列

题目

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
示例 1：
1
2
输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
示例 2：
1
2
输入：nums = [4,4,3,2,1]
输出：[[4,4]]
提示：
- 1 <= nums.length <= 15
- -100 <= nums[i] <= 100

思路

这个递增子序列比较像是取有序的子集。而且本题也要求不能有相同的递增子序列。
- 这又是子集，又是去重，让人不由自主的想起了刚刚讲过的 90.子集II (opens new window)。
就是因为太像了，更要注意差别所在，要不就掉坑里了！

在 90.子集II (opens new window) 中我们是通过排序，先让原数组中相同的元素挨在一起，再加一个标记数组来达到去重的目的。而本题求自增子序列，是不能对原数组进行排序的，因为排完序的数组都是自增子序列了。

所以不能使用之前的去重逻辑！本题给出的示例，还是一个有序数组 [4, 6, 7, 7]，这更容易误导大家按照排序的思路去做了。为了有鲜明的对比，用 [4, 7, 6, 7] 这个数组来举例，抽象为树形结构如图：

491. 递增子序列1

在图中可以看出，同一父节点下的同层上使用过的元素就不能再使用了

class Solution {
    private List<List<Integer>> res = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();

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

    public void backtracking(int[] nums, int startIndex) {
        if (path.size() >= 2) {
            res.add(new ArrayList<>(path));
        }
        if (startIndex >= nums.length) {
            return;
        }
        boolean[] used = new boolean[201]; // 因为题目限制-100 <= nums[i] <= 100
        for (int i = startIndex; i < nums.length; i++) {
            if ((!path.isEmpty() && path.get(path.size() - 1) > nums[i])
                || used[nums[i] + 100]) {
                continue;
            }
            path.add(nums[i]);
            used[nums[i] + 100] = true; // 用于限制同一父节点下的同层上使用过的元素不能再被使用
            backtracking(nums, i + 1);
            path.remove(path.size() - 1); // 回溯
        }
    }
}

注意这题和 90.子集II (opens new window) 的关系：
1. 这题要求递增子序列，那么就不能对原数据进行修改，即不能对原数组进行排序。
2. 由于求递增子序列这个要求，潜在地把一些重复的子集给过滤掉了，例如有子集 [1, 4]，而不会有子集 [4, 1]，所以用上面的代码是可以对本题进行求解的。同时，上面的方法同样可以求解 90.子集II (opens new window)，因为上面的代码可以保证同一父节点下的同层上使用过的元素不能再被使用，但是需要注意，在用上面的代码求解 90.子集II (opens new window) 问题时，同样需要先对原数组进行排序，如果没有对数组提前进行排序，例如对于数组 [4, 1, 4]，如果没有排序，那么用上面的代码，子集 [4, 1] 和子集 [1, 4] 都会出现，就出现子集重复的问题。
  - 从效率来看，还是
    1
    2
    3
    4
    // 方法一
    if (i > 0 && nums[i - 1] == nums[i] && used[i - 1] == false) {
    continue;
    }
    的效率要高于
    1
    2
    3
    4
    // 方法二
    if (set.contains(nums[i])) { // 用set集合代替used数组进行判断
    continue;
    }
  - 因为方法一中 used 数组是全局变量，方法二中 set 集合是局部变量，前者空间复杂度为 O(n)，后者空间复杂度为 O(n^2)。另外，判断元素是否在集合中，需要频繁地使用哈希函数进行映射，也会增加执行时间。

8.全排列

题目

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。你可以 按任意顺序 返回答案。
示例 1：
1
2
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
1
2
输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：
1
2
输入：nums = [1]
输出：[[1]]
提示：
- 1 <= nums.length <= 6
- -10 <= nums[i] <= 10
- nums 中的所有整数 互不相同

思路

回溯法三部曲：

递归函数的返回值以及参数
- 首先排列是有序的，也就是说 [1,2] 和 [2,1] 是两个集合，这和之前分析的子集以及组合所不同的地方。
- 可以看出元素 1 在 [1,2] 中已经使用过了，但是在 [2,1] 中还要在使用一次 1，所以处理排列问题就不用使用 startIndex 了。
  但排列问题需要一个 used 数组，标记已经选择的元素，如图橘黄色部分所示：
1
2
3
List<List<Integer>> result; // 存放符合条件结果的集合
List<Integer> path; // 用来存放符合条件单一结果
void backtracking(int[] nums, boolean[] used);
回溯函数终止条件
- 什么时候到达所谓的叶子结点了呢？
  - 当收集元素的数组 path 的大小达到和 nums 数组一样大的时候，说明找到了一个全排列，也表示到达了叶子结点。
1
2
3
4
if (path.size() == nums.length) {
result.add(path);
return;
}

单层搜索的过程

因为排列问题，每次都要从头开始搜索，例如元素 1 在 [1,2] 中已经使用过了，但是在 [2,1] 中还要再使用一次 1。而 used 数组，其实就是记录此时 path 里都有哪些元素使用了，一个排列里一个元素只能使用一次。

for (int i = 0; i < nums.length; i++) {
    if (used[i] == true) continue; // path里已经收录的元素，直接跳过
    used[i] = true;
    path.add(nums[i]);
    backtracking(nums, used);
    path.remove(path.size() - 1); // 回溯
    used[i] = false; // 回溯
}

class Solution {
    private List<List<Integer>> result = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        boolean[] used = new boolean[nums.length];
        // 初始化used数组
        for (int i = 0; i < used.length; i++) {
            used[i] = false;
        }
        backTracking(nums, used);
        return result;
    }

    public void backTracking(int[] nums, boolean[] used) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            backTracking(nums, used);
            path.remove(path.size() - 1); // 回溯
            used[i] = false; // 回溯
        }
    }
}

不用 used 数组，用 contains 方法判断元素是不是在 path 中就可以。

class Solution {
    private List<List<Integer>> result = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        backTracking(nums);
        return result;
    }

    public void backTracking(int[] nums) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (path.contains(nums[i])) {
                continue;
            }
            path.add(nums[i]);
            backTracking(nums);
            path.remove(path.size() - 1); // 回溯
        }
    }
}

8.1 全排列 II(去重)

题目

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
1
2
3
4
5
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
示例 2：
1
2
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
提示：
- 1 <= nums.length <= 8
- -10 <= nums[i] <= 10

思路

这道题目和 46.全排列 (opens new window) 的区别在于给定一个可包含重复数字的序列，要返回所有不重复的全排列。这里又涉及到去重了。
- 在 40.组合总和II (opens new window)、90.子集II (opens new window) 中详细讲解了组合问题和子集问题如何去重。那么排列问题其实也是一样的套路。
- 还要强调的是去重一定要对元素进行排序，这样我们才方便通过相邻的节点来判断是否重复使用了。

以示例中的 [1,1,2]为例（为了方便举例，已经排序）抽象为一棵树，去重过程如图：

47.全排列II1

图中我们对同一树层，前一位（也就是nums[i-1]）如果使用过，那么就进行去重。

一般来说：组合问题和排列问题是在树形结构的叶子节点上收集结果，而子集问题就是取树上所有节点的结果。

class Solution {
    private List<List<Integer>> res = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums); // 去重问题一定要对数组元素进行排序,使得相同值的元素挨在一起
        boolean[] used = new boolean[nums.length];
        backtracking(nums, used);
        return res;
    }

    public void backtracking(int[] nums, boolean[] used) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        // used[i - 1] == true，说明同⼀树⽀nums[i - 1]使⽤过
        // used[i - 1] == false，说明同⼀树层nums[i - 1]使⽤过
        // 如果同⼀树层nums[i - 1]使⽤过(used[i - 1] == false)则直接跳过
        // 如果当前元素使用过也直接跳过(used[i] == true)
        for (int i = 0; i < nums.length; i++) {
            if (used[i] || (i > 0 && nums[i - 1] == nums[i] && used[i - 1] == false)) {
                continue;
            }
            path.add(nums[i]);
            used[i] = true;
            backtracking(nums, used);
            path.remove(path.size() - 1); // 回溯
            used[i] = false; // 回溯
        }
    }
}

9.重新安排行程

题目

给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。

假定所有机票至少存在一种合理的行程。且所有的机票必须都用一次且只能用一次。

示例 1：

1 2	输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]] 输出：["JFK","MUC","LHR","SFO","SJC"]

示例 2：

1
2
3

输入：tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"] ，但是它字典排序更大更靠后。

提示：

1 <= tickets.length <= 300
tickets[i].length == 2
fromi.length == 3
toi.length == 3
fromi 和 toi 由大写英文字母组成
fromi != toi

思路

这道题目有几个难点：
1. 一个行程中，如果航班处理不好容易变成一个圈，成为死循环
2. 使用回溯法（也可以说深搜）的话，那么终止条件是什么呢？
3. 如何按字典排序返回最小的行程组合？
对于死循环，举一个有重复机场的例子：
- 如果在解题的过程中没有对集合元素处理好，就会死循环。可能出现下面的情况：
  1
  ["JFK","NRT","JFK","NRT","JFK","NRT","JFK"......]
- 所以需要定义一个 used 数组，来判断机票是否已经使用过。
使用回溯法的话，那么终止条件是什么呢？
- 以题目中的示例 1 为例，输入: [[“MUC”, “LHR”], [“JFK”, “MUC”], [“SFO”, “SJC”], [“LHR”, “SFO”]] ，这是有 4 个航班，那么只要找出一种行程，行程里的机场个数是 5 就可以了。
- 所以终止条件是：我们回溯遍历的过程中，遇到的机场个数，如果达到了（航班数量 +1），那么我们就找到了一个行程，把所有航班串在一起了。

如何按字典排序返回最小的行程组合？

直观的想法，对所有的机票，按降落的机场地点进行排序，然后在递归函数的单层逻辑中使用 for 循环即可。

class Solution {
    private List<String> res = new ArrayList<>();

    public List<String> findItinerary(List<List<String>> tickets) {
        Collections.sort(tickets, (a, b) -> a.get(1).compareTo(b.get(1))); // 来满足字典排序
        boolean[] used = new boolean[tickets.size()]; // used数组用于判断机票是否使用过
        res.add("JFK");
        backtracking(tickets, used);
        return res;
    }

    public boolean backtracking(List<List<String>> tickets, boolean[] used) {
        if (res.size() == tickets.size() + 1) {
            return true;
        }
        for (int i = 0; i < tickets.size(); i++) {
            if (!used[i] && tickets.get(i).get(0).equals(res.get(res.size() - 1))) {
                res.add(tickets.get(i).get(1));
                used[i] = true;
                if (backtracking(tickets, used)) {
                    return true; // 找到了解就不断return true退出递归，而不是往下回溯
                };
                res.remove(res.size() - 1);
                used[i] = false;
            }
        }
        return false;
    }
}

结果发现超时了，原因在于使用 sort 方法对机票进行排序时，消耗时间过长。

为了减少执行时间，考虑用空间换时间，不使用 List<List<String>> tickets 直接进行处理，而是使用 Map 来存储机票信息：

map<出发机场, map<到达机场, 航班次数>>，注意相同的机票是可能有多张的，比如从 JFK 到 NRT 的机票有两张这种。
具体来说，是 HashMap<出发机场, TreeMap<到达机场, 航班次数>>，用 TreeMap 来满足字典排序。

class Solution {
    private LinkedList<String> res = new LinkedList<>();
    // map<出发机场, map<到达机场, 航班次数>>
    private Map<String, Map<String, Integer>> map = new HashMap<>();

    public List<String> findItinerary(List<List<String>> tickets) {
        // 初始化map
        for (List<String> t : tickets) {
            String from = t.get(0);
            String to = t.get(1);
            Map<String, Integer> temp;
            if (map.containsKey(from)) {
                temp = map.get(from);
                temp.put(to, temp.getOrDefault(to, 0) + 1);
            } else {
                temp = new TreeMap<>(); // 默认升序
                temp.put(to, 1);
                map.put(from, temp);
            }
        }
        res.add("JFK");
        backtracking(tickets.size());
        return res;
    }

    public boolean backtracking(int ticketsNum) {
        if (res.size() == ticketsNum + 1) {
            return true;
        }
        String last = res.peekLast();
        if (map.containsKey(last)) {
            Map<String, Integer> temp = map.get(last); // 得到下一个要飞向的机场的集合
            for (Map.Entry<String, Integer> e : temp.entrySet()) {
                String to = e.getKey(); // 通过TreeMap来保证取出的到达机场是按字典排序的
                Integer count = e.getValue();
                if (count > 0) {
                    res.add(to);
                    temp.put(to, count - 1);
                    if (backtracking(ticketsNum)) {
                        return true;
                    }
                    res.removeLast(); // 回溯
                    temp.put(to, count); // 回溯，注意这里回溯是将count设置回原来的值，而不是count + 1
                }
            }
        }
        return false;
    }
}

10.N皇后

题目

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1：
1
2
3
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
1
2
输入：n = 1
输出：[["Q"]]
提示：
- 1 <= n <= 9

思路

N 皇后问题是经典的用回溯算法解决的问题。
首先来看一下皇后们的约束条件：
1. 不能同行
2. 不能同列
3. 不能同斜线
确定完约束条件，来看看究竟要怎么去搜索皇后们的位置，其实搜索皇后的位置，可以抽象为一棵树。
以一个 3 * 3 的棋盘为例，将搜索过程抽象为一棵树，如图：
从图中，可以看出，二维矩阵中矩阵的高就是这棵树的高度，矩阵的宽就是树形结构中每一个节点的宽度。
那么我们用皇后们的约束条件，来回溯搜索这棵树，只要搜索到了树的叶子节点，说明就找到了皇后们的合理位置了。

class Solution {
    private List<List<String>> res = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        char[][] chessboard = new char[n][n];
        // 初始化棋盘
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                chessboard[i][j] = '.';
            }
        }
        backtracking(n, 0, chessboard);
        return res;
    }

    public void backtracking(int n, int row, char[][] chessboard) {
        if (row == n) {
            res.add(arrayToList(n, chessboard));
            return;
        }

        for (int i = 0; i < n; i++) {
            if (isValid(n, row, i, chessboard)) {
                chessboard[row][i] = 'Q';
                backtracking(n, row + 1, chessboard);
                chessboard[row][i] = '.'; // 回溯
            }
        }
    }

    // 判断皇后的位置是否可行
    public boolean isValid(int n, int row, int col, char[][] chessboard) {
        // 隐含的已经不可能在同一行了
        // 判断是否在同一列
        for (int i = 0; i < row; i++) {
            if (chessboard[i][col] == 'Q') {
                return false;
            }
        }
        // 判断是否在45度角的斜线上
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }
        // 判断是否在135度角的斜线上
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }

    public List<String> arrayToList(int n, char[][] chessboard) {
        List<String> temp = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            temp.add(new String(chessboard[i]));
        }
        return temp;
    }
}

11.解数独

题目

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1：

1
2
3

输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

提示：

board.length == 9
board[i].length == 9
board[i][j] 是一位数字或者 '.'
题目数据保证输入数独仅有一个解

思路

棋盘搜索问题可以使用回溯法暴力搜索，只不过这次我们要做的是二维递归。
- 我们之前做的题目例如：77.组合（组合问题） (opens new window)，131.分割回文串（分割问题） (opens new window)，78.子集（子集问题） (opens new window)，46.全排列（排列问题） (opens new window)，以及51.N皇后（N皇后问题） (opens new window)，其实这些题目都是一维递归。
本题就不一样了，本题中棋盘的每一个位置都要放一个数字（而N皇后是一行只放一个皇后），并检查数字是否合法，解数独的树形结构要比N皇后更宽更深。如图所示：
回溯三部曲：
1. 确定回溯函数及参数：
  - 本题递归函数的返回值需要是 boolean 类型，为什么呢？
    - 因为解数独找到一个符合的条件（就在树的叶子节点上）就立刻就返回，相当于找从根节点到叶子节点一条唯一路径，所以需要使用 boolean 返回值。如果返回为 true 就不需要再执行后续的回溯代码了。
2. 确定递归终止条件
  - 本题递归不用终止条件，解数独是要遍历整个树形结构寻找可能的叶子节点就立刻返回。
  - 递归的下一层的棋盘一定比上一层的棋盘多一个数，等数填满了棋盘自然就终止（填满当然好了，说明找到结果了），所以不需要终止条件！
3. 确定单层递归逻辑
  - 在树形图中可以看出我们需要的是一个二维的递归（一行一列）
  - 一个 for 循环遍历棋盘的行，一个 for 循环遍历棋盘的列，一行一列确定下来之后，递归遍历这个位置放 9 个数字的可能性！
判断棋盘是否合法有如下三个维度：
- 同行是否重复
- 同列是否重复
- 9宫格里是否重复

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

    public boolean backtracking(char[][] board) {
        for (int row = 0; row < board.length; row++) { // 遍历行
            for (int col = 0; col < board[row].length; col++) { // 遍历列
                if (board[row][col] != '.') {
                    continue;
                }
                for (char k = '1'; k <= '9'; k++) {
                    if (isValid(board, k, row, col)) {
                        board[row][col] = k;
                        if (backtracking(board)) {
                            return true; // 表明已经找到了解，直接返回，不需要再回溯了
                        }
                        board[row][col] = '.'; // 回溯
                    }
                }
                return false; // 如果数字1-9试过都不可以，就返回false
            }
        }
        return true; // 表明表格已经填满，则返回true
    }

    public boolean isValid(char[][] board, char k, int row, int col) {
        // 判断行合法
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == k) {
                return false;
            }
        }
        // 判断列合法
        for (int i = 0; i < 9; i++) {
            if (board[i][col] == k) {
                return false;
            }
        }
        // 判断3x3宫内合法
        int startRow = row / 3 * 3;
        int startCol = col / 3 * 3;
        for (int i = startRow; i < startRow + 3; i++) {
            for (int j = startCol; j < startCol + 3; j++) {
                if (board[i][j] == k) {
                    return false;
                }
            }
        }
        return true;
    }
}