LeetCodeCampsDay25回溯part04

491是去重复的另一种情况，此时是不能将数组先排序再判断

491. 非递减子序列

https://leetcode.cn/problems/non-decreasing-subsequences/

给你一个整数数组 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有点像，但不同点是，本题不让排序，就没法使用nums[i] == nums[i - 1]来判断某个数字是否在本层被用过了，但记住，去重的核心思路是：当前数字num[i]是否在num[start: i]（不包含i）出现过，如果没出现过就可以用，否则continue，比如[7, 6, 7]，需要判断第二个7（即nums[i]，是否在nums[start: i]里）；

此外，还有个剪枝的条件，如果path的最后一个值比num[i]大，则可以跳过；

  1. 输入输出：输入列表，开始下标；无返回值
  2. 终止条件：如果path长度大于2个就添加，无其它条件（单层逻辑必须保证此时是满足题目要求的）
  3. 单层逻辑：先去重，再剪枝掉path的最后一个值比num[i]大情况（可以不做，因为isLegal函数也会处理），随后，将当前数字添加到path并使用isLegal函数判断path是否合规，如果全规则再递归其子串；

img

回溯代码

  • 时间复杂度O(N * 2^N)
  • 空间复杂度O(N)
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
37
38
39
40
class Solution:
    def __init__(self):
        self.res = list()
        self.path = list()
    
    def islegal(self, nums: List[int]) -> bool:
        L = len(nums)
        # 需要保证nums[i + 1] >= nums[i]
        for i in range(1, L):
            if nums[i] < nums[i - 1]:
                return False
        return True

    def foo(self, nums: List[int], startIndex: int = 0):
        if len(self.path) > 1:
            self.res.append(self.path[:])

        # print(self.path)
        for i in range(startIndex, len(nums)):
            # 去重
            # 不能用nums[i] == nums[i - 1]来判断，因为能用这个去重的前提是有序的数组，而这题目是无序的
            # 但需要判断当前nums[i]是否在这层之前出现过
            # 比如[7, 6, 7]，需要判断第二个7（即nums[i]，是否在nums[start: i]里）
            if nums[i] in nums[startIndex: i] and i > startIndex:
                continue
            # 剪枝
            if len(self.path) > 1 and self.path[-1] > nums[i]:
                continue
            # 
            self.path.append(nums[i])
            # print(self.path)        
            if self.islegal(self.path[:]):
                self.foo(nums, i + 1)
            self.path.pop()

    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        # 本题似乎不能直接对nums排序，和子集II思路不同
        # 需要个子函数判断当前path里的是否合规
        self.foo(nums)
        return self.res

46. 全排列

https://leetcode.cn/problems/permutations/

给定一个不含重复数字的数组 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 中的所有整数 互不相同

回溯思路

画个二叉树的图后，可以发现，随着递归深度增加，for循环遍历的对象是未在path里的元素，所以需要有个used表来记录哪些元素被访问过；可以使用dict或者list实现

  1. 输入输出：输入列表，无返回值
  2. 终止条件：当path长度等于nums长度则添加到res，如果path长度大于nums长度直接退出
  3. 单层逻辑：for循环遍历的对象是未在path里的元素，所以是for i in range(len(nums))；并且需要判断是否被访问过，只递归未访问过的元素

回溯代码

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:
    def __init__(self):
        self.res = list()
        self.path = list()
        self.avoidIndex = dict()

    def foo(self, nums: List[int]):
        if len(self.path) == self.targetLen:
            self.res.append(self.path[:])
        if len(self.path) > self.targetLen:
            return

        for i in range(len(nums)):
            if self.avoidIndex.get(nums[i], 0) != 0:
                continue
            # 或者使用列表
            # if self.avoidIndex[i] != 0:
            #    continue
            self.avoidIndex[nums[i]] = 1
            self.path.append(nums[i])
            self.foo(nums)
            self.path.pop()
            self.avoidIndex[nums[i]] = 0

    def permute(self, nums: List[int]) -> List[List[int]]:
        self.targetLen = len(nums)
        # 全排列的树和组合类型的树不太一样，不需要使用startIndex，然而它for循环的被迭代对象是"不在path里的所有元素"
        self.foo(nums)
        return self.res

47. 全排列 II

https://leetcode.cn/problems/permutations-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

回溯思路

本题目和47.全排列II的不同点是“本题有可重复数字”，面对可重复数字，就需要去重复（比如先排序，再用nums[i]==nums[i-1]判断）；另一方面，本题也需要和一样，需要使用used数组来保证递归时只遍历“剩下”的子串（纵向条件）

  1. 输入输出：输入列表，无直接返回值
  2. 终止条件：当path长度与nums长度相等即添加到res
  3. 单层逻辑：纵向上，只遍历剩余字符串；横向上，需要先去重复，再进行（标记当前数字被use->添加到path-> 递归下一层 -> 从path弹出回溯-> 标记当前数字未被use)
  4. 这是去重复使用if i > 0 and nums[i] == nums[i - 1] and self.used[i - 1] == 0: continue，注意这里的self.used[i - 1] == 0，表示只有nums[i - 1]被用过了，而且nums[i]==nums[i-1]时，才能执行for单层逻辑，否则就跳过当前数字，因为当nums[i - 1]未被用过时，则nums[i - 1]就已经包含了nums[i]的情况（可以看下面的图）

还要强调的是去重一定要对元素进行排序，这样我们才方便通过相邻的节点来判断是否重复使用了。

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

img

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

在46.全排列 (opens new window)中已经详细讲解了排列问题的写法，在40.组合总和II (opens new window)、90.子集II (opens new window)中详细讲解了去重的写法

回溯代码

  • 时间复杂度: O(n! * n)
  • 空间复杂度: O(n)
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
class Solution:
    def __init__(self):
        self.res = list()
        self.path = list()
    
    def foo(self, nums):
        if len(self.path) == self.targetLen:
            self.res.append(self.path[:])
        
        for i in range(len(nums)):
          	# 这个used是保证递归时只遍历“剩下”的子串（纵向条件）
            if self.used[i] == 1:
                continue
            # 这个是保证去重复（横向条件），不能只用nums[i] == nums[i - 1]，否则例如输入：[1,1,2]，则不会有"112"这样的输出
            if i > 0 and nums[i] == nums[i - 1] and self.used[i - 1] == 0:
                continue
            # 需要再添加个self.used[i - 1] == 0条件，即，只有num[i - 1]被用过了，而且num[i]==num[i-1]时，才能执行for单层逻辑
            self.used[i] = 1
            self.path.append(nums[i])
            self.foo(nums)
            self.path.pop()
            self.used[i] = 0

    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        # 先对nums排序，再判断nums[i]是否等于nums[i-1]
        nums = sorted(nums)
        self.targetLen = len(nums)
        self.used = [0] * self.targetLen
        self.foo(nums)
        return self.res

反思

大家发现，去重最为关键的代码为：

1
2
3
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
    continue;
}

如果改成 used[i - 1] == true， 也是正确的!，去重代码如下：

1
2
3
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == true) {
    continue;
}

这是为什么呢，就是上面我刚说的，如果要对**树层中前一位（横向）去重，就用used[i - 1] == false，如果要对树枝前一位（纵向）**去重用used[i - 1] == true。

对于排列问题，树层上去重（横向）和树枝上去重（纵向），都是可以的，但是树层上去重效率更高！

这么说是不是有点抽象？

来来来，我就用输入: [1,1,1] 来举一个例子。

树层上去重(used[i - 1] == false)的树形结构如下：

47.全排列II2

树枝上去重（used[i - 1] == true）的树型结构如下：

47.全排列II3

大家应该很清晰的看到，树层上对前一位（横向）去重非常彻底，效率很高，树枝上对前一位去（纵向）重虽然最后可以得到答案，但是做了很多无用搜索。

51. N 皇后

https://leetcode.cn/problems/n-queens/

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

img

1
2
3
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

1
2
输入：n = 1
输出：[["Q"]]

提示：

  • 1 <= n <= 9

回溯思路

本方法特点：不创建初始棋盘，并且isValid函数也无需对整个棋盘进行遍历

在做了前面的全排列与各种子集问题后，这题目反而不难，完全可以按下面的图，把代码写出来；横向遍历+纵向遍历，仍然使用path记录路径，此外，需要一个判别函数islegal()判断当前位置是否合规（在491.非递减子序列和93. 复原 IP 地址 也使用了islegal函数）

  1. 输入输出：输入棋盘长度，无直接返回值
  2. 终止条件：当path长度与棋盘长度一致，返回结果
  3. 单层逻辑：横向遍历(for循环里)，先判断当前位置(depth, x)是否合规，其中depth指纵向深度下标，x指横向下标；如果合规，再将(depth, x)添加到path里，递归下一个深度，从path弹出回溯。（这里可以仅将x添加到path里，因为depth和x的下标是一样的）
  4. islegal判断条件：
    1. 函数功能：当前位置的上边列、左上角、右上角没有数字；
    2. 输入输出：输入位置(depth, x) ，输出bool
    3. 不像以往那种，先创建个棋盘，再对棋盘进行遍历；我们仅需要对path和当前位置进行判断即可，对path里的每个元素i遍历
      1. 假设path记录的是坐标（[0,0], [1,2]），对于一个当前位置[2,0]
      2. if i[1] == x， 说明当前列(x) 上边有元素，返回False
      3. if depth - i[0] == x - i[1]，说明当前位置左上角有元素，返回False
      4. if depth - i[0] == i[1] - x，说明当前位置右上角有元素，返回False

判断函数甚至可以精简成这样（但这样就看不出来动机了）

1
2
3
4
5
def isLegal(self, depth, col) -> bool:
    for i in self.path:
        if i[1] == col or depth - i[0] == abs(col - i[1]):
            return False
    return True

注意，本方法不需要对当前行的左边进行判断，因为进入当前行时，左边一定是不会有元素的 我们总是从上到下处理每一行（例如，从行 0 到行 N-1）。
当我们到达第 ⁠depth 行时，⁠self.path 中只包含之前行（0 到 depth-1）的皇后位置

img

回溯代码

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution:
    def __init__(self):
        self.res = list()
        self.path = list()
    
    # 当前path记录的是坐标（比如[0,0], [1,2]），传入的是位置[2,0]
    def isLegal(self, depth, col) -> bool:
        for i in self.path:
        # 同一行的左边列是否有皇后
        # 我们到达第 ⁠depth 行时，⁠self.path 中只包含之前行（0 到 depth-1）的皇后位置
        # 所以不用判断
            # if i[0] == depth:
                # return False

        # 同一列的上边行是否有皇后
            if i[1] == col:
                return False

        # 若左上角有皇后
            if depth - i[0] == col - i[1]:
                return False
        
        # 若右上角有皇后
            if depth - i[0] == i[1] - col:
                return False

        return True
    
    def list2res(self, path: List) -> str:
        # 创建个长度为len(path)的字符
        board = list()
        L = len(path)
        for i in path:
            board.append("."*(i[1]) + "Q" + "."*(L - i[1] - 1))
        return board

    def foo(self, n: int, depth: int = 0):
        # 终止条件：深度depth等于n时即可退出
        if depth == n:
            self.res.append(self.list2res(self.path[:]))
        
        # 横向遍历col
        for col in range(n):
            if self.isLegal(depth, col):
                # path其实可以用记录col，depth本身等于col下标
                self.path.append([depth, col])
                self.foo(n, depth + 1)
                self.path.pop()
        

    def solveNQueens(self, n: int) -> List[List[str]]:
        self.foo(n)
        return self.res

回溯改进思路

为了判断一个位置所在的列和两条斜线上是否已经有皇后，使用三个集合 columns、diagonals1 和 diagonals2 分别记录每一列以及两个方向的每条斜线上是否有皇后。

列的表示法很直观，一共有 N 列，每一列的下标范围从 0 到 N−1，使用列的下标即可明确表示每一列。

如何表示两个方向的斜线呢？对于每个方向的斜线，需要找到斜线上的每个位置的行下标与列下标之间的关系。

方向一的斜线为从左上到右下方向，同一条斜线上的每个位置满足行下标与列下标之差相等，例如 (0,0) 和 (3,3) 在同一条方向一的斜线上。因此使用行下标与列下标之差即可明确表示每一条方向一的斜线。

回溯代码2

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
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution:
    def __init__(self):
        self.res = list()
        self.path = list()
        self.cols = set()
        self.diag1 = set()
        self.diag2 = set()
    
    # 当前path记录的是坐标（比如-[0,0], [1,2]），对于一个节点[2,0]
    def isLegal(self, depth, x) -> bool:
        
        if x in self.cols:
            return False
        if depth + x in self.diag1:
            return False
        if depth - x in self.diag2:
            return False
        return True
    
    def list2res(self, path: List) -> str:
        # 创建个长度为len(path)的字符串，对i in path，
        board = list()
        L = len(path)
        for i in path:
            board.append("."*(i[1]) + "Q" + "."*(L - i[1] - 1))
        return board

    def foo(self, n: int, depth: int = 0):
        # 终止条件：深度y等于n时即可退出
        if depth == n:
            self.res.append(self.list2res(self.path[:]))
        
        # 横向遍历x
        for x in range(n):
            if self.isLegal(depth, x):
                self.path.append([depth, x])
                self.cols.add(x)
                self.diag1.add(depth + x)
                self.diag2.add(depth - x)
                self.foo(n, depth + 1)
                self.cols.remove(x)
                self.diag1.remove(depth + x)
                self.diag2.remove(depth - x)
                self.path.pop()
        

    def solveNQueens(self, n: int) -> List[List[str]]:
        self.foo(n)
        return self.res

52. N 皇后 II

https://leetcode.cn/problems/n-queens-ii/

n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。

示例 1：

img

1
2
3
输入：n = 4
输出：2
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

1
2
输入：n = 1
输出：1

提示：

  • 1 <= n <= 9

回溯代码

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
class Solution:
    def __init__(self):
        self.res = 0
        self.path = list()
    
    # 当前path记录的是坐标（比如[0,0], [1,2]），传入的是位置[2,0]
    def isLegal(self, depth, col) -> bool:
        for i in self.path:
            if i[1] == col or depth - i[0] == abs(col - i[1]):
                return False
        return True

    def foo(self, n: int, depth: int = 0):
        # 终止条件：深度depth等于n时即可退出
        if depth == n:
            self.res += 1
        
        # 横向遍历col
        for col in range(n):
            if self.isLegal(depth, col):
                # path其实可以用记录col，depth本身等于col下标
                self.path.append([depth, col])
                self.foo(n, depth + 1)
                self.path.pop()

    def totalNQueens(self, n: int) -> int:
        self.foo(n)
        return self.res

332. 重新安排行程

https://leetcode.cn/problems/reconstruct-itinerary/

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

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

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

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

示例 1：

img

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

示例 2：

img

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

回溯思路

这个方法有点儿怪，题目要求从JFK出发并且绕完所有的机场，题目保证一定有解；所以只要从JFK出发，遍历它能到达的落地节点，再从落地节点出发，遍历落地节点的落地节点……比如，JFK->KUL，到达KUL则终点了，此时将KUL添加到res里；随后遍历JFK->NRT，NRT->JFK，又到了JFK，但此时JFK已经飞过了KUL和NRT（相当于没有从JFK的票了)，于是此时JFK(作为落地节点)被添加到res里；回到NRT，它也没有其它落地节点了，它被添加到res；最后回到JFK(作为初始的出发节点)也被添加到res里。

  1. 回溯的输入输出：输入出发机场和现有的机票，无直接输出
  2. 终止条件：当前出发的机场没有机票时停止，此时将当前机场添加到res里
  3. 单层逻辑：遍历当前出发的机场所有机票，如果有票，先消耗这张票，递归（纵向遍历）这个票的终点机场；注意，这里没有回溯，即，不会把消耗的机票还原回去，试想下，如果还原回去，此时就会进入无尽的循环。

![image-20250720211959981](/Users/lthero/Library/Application Support/typora-user-images/image-20250720211959981.png)

回溯代码

  • 时间复杂度O(nLogN)
  • 空间复杂度O(N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def __init__(self):
        self.res = []

    def foo(self, airport, targets):
        while targets[airport]:
            next_airport = targets[airport].pop()
            self.foo(next_airport, targets)
        # 当前出发的机场没有机票时停止，此时将当前机场添加到res里
        self.res.append(airport)

    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        from collections import defaultdict

        targets = defaultdict(list)
        for ticket in tickets:
            targets[ticket[0]].append(ticket[1])
        
        for key in targets:
            targets[key].sort(reverse = True)
        
        self.foo("JFK", targets)
        return self.res[::-1]

37. 解数独

https://leetcode.cn/problems/sudoku-solver/

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

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

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

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

示例 1：

img

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皇后问题 (opens new window)是因为每一行每一列只放一个皇后，只需要一层for循环遍历一行，递归来遍历列，然后一行一列确定皇后的唯一位置。

本题就不一样了，本题中棋盘的每一个位置都要放一个数字（而N皇后是一行只放一个皇后），并检查数字是否合法，解数独的树形结构要比N皇后更宽更深。

数独的树

  1. 输入输出：输入棋盘，输出bool，表示如果找到解就直接一路return，不用继续搜索了
  2. 终止条件：本题递归不用终止条件，解数独是要遍历整个树形结构寻找可能的叶子节点就立刻返回。
  3. 单层逻辑：横向遍历是对棋盘的高、宽进行二维遍历，此外还需要对数字(1~9)进行逐个横向遍历，仅只有当前位置上(row, col)填写数字i是合规的情况下，才能纵向遍历
    1. 先判断当前位置是否数字，如果是则跳过
    2. 判断当前位置的数字i是否合规，如果合规，则将board的当前位置更新为这个数字i，再纵向遍历（递归），最后回溯将board当前位置更新为’.’
  4. 判断当前位置的数字是否合规
    1. 判断是否同行、同列、是否同一个小九宫格
    2. 注意小九宫格的判断方法，先求这个小九宫格里的行、列开始坐标，再此坐标上加三即可

回溯代码

下面代码会超时，但思路是正确的，超时的原因是九宫格判断，如果要遍历整个棋盘，会浪费大量时间

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution:
    def __init__(self):
        pass
    
    def islegal(self, row: int, col: int, num: str) -> bool:
        # 判断同行
        for i in range(self.W):
            if self.board[row][i] == num:
                return False
        # 判断同列
        for i in range(self.H):
            if self.board[i][col] == num:
                return False

        # 判断九宫格内
        # 先得到num所在的九宫格
        rowStart = (row // 3) * 3
        colStart = (col // 3) * 3

        for i in range(rowStart, rowStart + 3):
            for j in range(colStart, colStart + 3):
                if self.board[i][j] == num:
                    return False

        return True

    def foo(self):
        for row in range(self.H):
            for col in range(self.W):
                if self.board[row][col] != '.':
                    continue
                for i in range(1, 10):
                    if self.islegal(row, col, str(i)):
                        self.board[row][col] = str(i)
                        if self.foo():
                            return True
                        self.board[row][col] = '.'
                return False
        return True

    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        self.board = board
        self.H = len(self.board)
        self.W = len(self.board[0])
        self.foo()
        return self.board

不超时版本，用空间换时间，给每行每列每个小九宫格添加个used数组，并且！不要使用函数调用！否则一定会超时

The inline condition is directly part of the loop in your ⁠backtracking method. The Python interpreter can execute it without any extra indirection. In contrast, a method call introduces a “jump” to another part of the code, which can slow things down.

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        self.row_used = [set() for _ in range(9)]
        self.col_used = [set() for _ in range(9)]
        self.box_used = [set() for _ in range(9)]
        self.board = board
        for row in range(9):
            for col in range(9):
                num = self.board[row][col]
                if num == ".":
                    continue
                self.row_used[row].add(num)
                self.col_used[col].add(num)
                self.box_used[(row // 3) * 3 + col // 3].add(num)
        self.backtracking(0, 0)
        
		def islegal(self, row: int, col: int, num: str):
        return (num not in self.row_used[row] and num not in self.col_used[col] and num not in self.box_used[(row // 3) * 3 + col // 3])

    def backtracking(
        self,
        row: int,
        col: int,
    ) -> bool:
        if row == 9:
            return True

        next_row, next_col = (row, col + 1) if col < 8 else (row + 1, 0)
        if self.board[row][col] != ".":
            return self.backtracking(
                next_row, next_col
            )

        for num in map(str, range(1, 10)):
          	# 不要使用函数调用，如果调用self.islegal(row, col, num)一定会超时
            if num not in self.row_used[row] and num not in self.col_used[col] and num not in self.box_used[(row // 3) * 3 + col // 3]:
                self.board[row][col] = num
                self.row_used[row].add(num)
                self.col_used[col].add(num)
                self.box_used[(row // 3) * 3 + col // 3].add(num)
                if self.backtracking(
                    next_row, next_col
                ):
                    return True
                self.board[row][col] = "."
                self.row_used[row].remove(num)
                self.col_used[col].remove(num)
                self.box_used[(row // 3) * 3 + col // 3].remove(num)
        return False