【算法题目】【Python】彻底刷遍DFS与回溯的算法题目

参考资料

参考这里面的一些讲解： https://github.com/youngyangyang04/leetcode-master。

热身：树的前序、中序、后序遍历

看完 树的种类 之后，就需要熟悉好树的遍历。

树的前序遍历leetcode：

DFS递归写法很重要，需要重点理解掌握：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res=[]
        def dfs(root):
            if not root:
                return
            res.append(root.val)
            dfs(root.left)
            dfs(root.right)
        dfs(root)
        return res

在树结构中，DFS可以搞定的，使用栈构成迭代法也是可以搞定的：

# 首先将根节点入栈，然后每次从栈顶取出一个节点，并将其值加入到结果列表中；
# 接着按照右-左-根的顺序将其子节点入栈。
# 由于栈是先进后出的结构，所以弹出左子节点时会优先处理它的子树，从而实现了前序遍历的效果。
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        stack = [root]
        while stack:
            node = stack.pop()
            if not node:
                continue
            res.append(node.val)
            stack.append(node.right)
            stack.append(node.left)
        return res

迭代法 中序遍历：

# 先将根节点及其所有左子节点入栈，然后每次从栈顶取出一个节点，并将其右子节点入栈，直到栈为空。由于出栈顺序为左-中-右，所以可得到中序遍历的结果
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        stack = []
        node = root
        while node or stack:
            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()
            res.append(node.val)
            node = node.right
        return res

迭代法后序遍历 和 迭代法前序遍历 写法类似：

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        stack = [root]
        while stack:
            node = stack.pop()
            if not node:
                continue
            res.append(node.val)
            stack.append(node.left)
            stack.append(node.right)
        return res[::-1]

热身：树的层次遍历

可以使用递归法写出：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        res=[]
        
        def dfs(root,depth):
            if not root:
                return []
            if len(res)==depth:res.append([])
            res[depth].append(root.val) # depth层的list进行append
            dfs(root.left, depth + 1)
            dfs(root.right, depth + 1)
        
        dfs(root,0)

        return res

也可以使用队列实现：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []

        result = []
        queue = [root]

        while queue:
            level_size = len(queue)
            current_level = []

            for i in range(level_size):  # 队列当前元素是这一层的Node，全部弹出
                node = queue.pop(0)
                current_level.append(node.val)

                if node.left:
                    queue.append(node.left)

                if node.right:
                    queue.append(node.right)

            result.append(current_level)

        return result

纯DFS与回溯法的区别

回溯法和不回溯的DFS都是搜索算法，它们的本质区别在于“状态重置”这一步骤。

• 回溯法：在搜索过程中，每次扩展新的节点时，我们先记录当前的状态或者做出选择，然后递归地访问子节点。当递归返回时，我们需要撤销刚才的选择或恢复之前的状态，以便让程序正确地执行下一个节点的遍历。也就是说，回溯法中的关键点是“状态重置”，并且实现方式一般是用栈来保存状态，用回溯来恢复状态。

• 不回溯的DFS：在搜索过程中，每次扩展新的节点时，我们直接生成一个新的状态或者做出选择，并将其作为参数传递给下一层函数进行递归调用。由于每个状态都是独立的，所以不需要进行状态的撤销或恢复操作，也就不需要回溯。实现方式是通过传递可变对象（如列表）来实现状态的更新。

在回溯法中，我们在递归调用之前做出了选择，并在递归返回后撤销了该选择，而在不回溯的DFS中，我们没有必要撤销该选择，因为我们每次都是创建一个新的状态/选择来进行递归调用。

纯DFS与回溯法的算法题目

关于树的算法题目很多，比如求树的深度、节点个数、删除节点等题目，都需要耐心刷完，这里主要关注DFS搜索和BFS搜索，依靠多刷一些题，总结出规律。

按DFS的思维遍历树的节点的时候，意识到DFS的思维是将总问题转为当前可解决的问题与一个子问题，且子问题的解决方式就是总问题，以此达到递归的目的。

按【代码随想录】的题目刷完：

组合

https://leetcode.cn/problems/combinations/：

只DFS:

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        nums = list(range(1, n+1))

        def dfs(start, path):
            if len(path) == k:
                res.append(path[:])
                return
            for i in range(start, n):
                dfs(i + 1, path + [nums[i]])

        dfs(0, [])
        return res

下面的解法思维会经常性使用，需要思考dfs的传参，思考何时停止条件，思考罗列所有状态：

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        nums = list(range(1, n+1))

        def backtrack(start, path): # 从哪里开始选元素，这个切入点很重要；当前选了什么元素，这个切入点也重要。
            # 如果当前的组合长度等于k，将其加入结果列表
            if len(path) == k:
                res.append(path[:])
                return
            
            # 遍历可选数字，并尝试将其加入组合中
            for i in range(start, n):
                path.append(nums[i])
                backtrack(i+1, path) # 从下个元素开始选
                path.pop()

        backtrack(0, [])
        return res

对于该问题，可以采用一些剪枝策略来优化搜索过程，减少不必要的计算。

一种常见的剪枝策略是 “剪去无法得到 k 个数字的组合”，具体实现为：在递归函数 backtrack 中，当 path 的长度加上从 start 到 n 的数字数量仍然小于 k 时，说明已经无法得到长度为 k 的组合了，此时直接返回即可。

另外，在枚举可选数字时，我们可以限制 i 的上限，以确保最后一个数字被选择时，剩余的数字数量也足够凑成长度为 k 的组合。具体实现为：在 for 循环中，将 i 的上限设置为 n - (k - len(path)) + 1。

剪枝是非常重要的策略，在这里测试的话可以降低时间复杂度7倍。 剪枝的本质就是要思考更多的递归停止条件 。

下面是使用上述两种剪枝策略的代码：

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        nums = list(range(1, n+1))

        def backtrack(start, path):
            # 如果当前的组合长度等于k，将其加入结果列表
            if len(path) == k:
                res.append(path[:])
                return
            
            # 剪枝：无法凑齐k个数字的组合
            if len(path) + n - start + 1 < k:
                return

            # 剪枝：i 的上限
            for i in range(start, n - (k - len(path)) + 2):
                path.append(nums[i-1])
                backtrack(i+1, path)
                path.pop()

        backtrack(1, [])
        return res

组合总和 III

https://leetcode.cn/problems/combination-sum-iii/description/

只DFS:

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        res = []
        
        def dfs(start, path, target):
            if target == 0 and len(path) == k:
                res.append(path)
                return
            if len(path) == k or target < 0:
                return
            for i in range(start, 10):
                dfs(i + 1, path + [i], target - i)
        
        dfs(1, [], n)
        return res

只用回溯：

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        res = []
        nums = [i for i in range(1, 10)]

        def dfs(start, path):
            if sum(path) == n and len(path) == k:
                res.append(path[:])
                return
            for i in range(start, len(nums)):
                path.append(nums[i])
                dfs(i + 1, path)  # 注意是i+1，不是start+1,start是固定的
                path.pop()

        dfs(0, [])
        return res

加上剪枝：
（1）path总和大于n的直接停止；
（2）i的上限；

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        res = []
        nums = [i for i in range(1, 10)]

        def dfs(start, path, target):
            if target < 0:
                return
            if len(path) == k and target == 0:
                res.append(path[:])
                return

            # 剪枝：i 的上限
            upper = min(8, target)  # 最大可选数字
            for i in range(start, upper + 1):
                if sum(path) + nums[i] > n or len(path) == k:
                    break
                path.append(nums[i])
                dfs(i + 1, path, target - nums[i])
                path.pop()

        dfs(0, [], n)
        return res

电话号码的字母组合

https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
Python暴力也很有味道：

    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        d = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
        res = [""]
        for i in digits:
            res = [x + y for x in res for y in d[i]]
        return res

此题的dfs也可以不需要回溯：

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        d = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
        res = []

        def dfs(start, path):  # 得益于Python的字符串加法，可以把当前字符串带入到下一次dfs，不用回溯记忆
            if len(path) == len(digits):
                res.append(path)
                return
            for i in range(start, len(digits)):  # 从start开始，因为start之前的已经处理过了s
                for j in d[digits[i]]:  # 选某一个字母
                    dfs(i + 1, path + j)

        dfs(0, "")
        return res

下面是回溯法的思路：

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return list()
        phoneMap = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }
        def backtrack(index: int):
            if index == len(digits):
                combinations.append("".join(combination))
                return
            digit = digits[index]
            for letter in phoneMap[digit]:
                combination.append(letter)
                backtrack(index + 1)
                combination.pop()
        combination = list()
        combinations = list()
        backtrack(0)
        return combinations

组合总和

https://leetcode.cn/problems/combination-sum/description/
dfs:

# 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
# candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []

        def dfs(candidates, target, path):
            if target < 0:
                return
            if target == 0:
                res.append(path)
                return
            print(candidates)
            for i in range(len(candidates)):
                dfs(candidates[i:], target - candidates[i], path + [candidates[i]])  # 传入的还是全部的备选

        dfs(candidates, target, [])
        return res

回溯法：

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        def dfs(candidates, begin, path, target):
            if target == 0:
                result.append(path[:])
                return
            if target < 0:
                return
            for i in range(begin, len(candidates)):
                path.append(candidates[i])
                dfs(candidates, i, path, target-candidates[i])
                path.pop()
        dfs(candidates, 0, [], target)
        return result

组合总和 II

https://leetcode.cn/problems/combination-sum-ii/description/
dfs:

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(start, target, path):
            if target == 0:
                res.append(path)
                return
            for i in range(start, len(candidates)):
                if i > start and candidates[i] == candidates[i-1]:
                    continue
                if candidates[i] > target:
                    break
                dfs(i+1, target-candidates[i], path+[candidates[i]])
        
        candidates.sort()
        res = []
        dfs(0, target, [])
        return res

回溯：

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        def backtrack(start, target, path):
            if target == 0:
                res.append(path[:])
                return
            for i in range(start, len(candidates)):
                # 剪枝条件：去重
                if i > start and candidates[i] == candidates[i-1]:
                    continue
                # 剪枝条件：大于目标值
                if candidates[i] > target:
                    break
                # 选择当前元素
                path.append(candidates[i])
                # 递归到下一层
                backtrack(i+1, target-candidates[i], path)
                # 撤销选择，回溯到上一层
                path.pop()
        
        # 排序，方便后续的去重操作
        candidates.sort()
        res = []
        backtrack(0, target, [])
        return res

分割回文串

https://leetcode.cn/problems/palindrome-partitioning/description/
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。

题目可能难以理解 ，一个用例：
输入：s = “aab”
输出：[[“a”,“a”,“b”],[“aa”,“b”]]
输出里每个子list都是一种分割方式，分割完之后，每个子串都是回文。

dfs:

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        res = []

        def isPalindrome(s):
            return s == s[::-1]

        def dfs(s, path):
            if not s:
                res.append(path)
                return
            for i in range(1, len(s) + 1):
                if isPalindrome(s[:i]):
                    dfs(s[i:], path + [s[:i]])

        dfs(s, [])
        return res

回溯：

我的方法和回溯法的思路比较相似，都是从字符串的起点开始枚举子串，并判断是否为回文串。不同之处在于，我的方法使用了深度优先搜索（DFS）来搜索所有可能的分割方案，而回溯法则更加显式地体现了“回溯”的过程。

具体来说，我的方法中的 dfs 函数会遍历所有满足条件的子串，并继续以当前位置的下一个位置为起点继续搜索下去，直到搜索到字符串的末尾。如果找到了一组可行的分割方案，就将其加入结果列表中。这个过程实际上就是一种深度优先搜索，它沿着某个可能的分割路径一步步往下走，直到无法继续前进时返回上一步。

相比之下，回溯法更加显式地体现了“回溯”的过程。具体来说，每当我们尝试加入一个新的子串，如果发现这个子串不能满足要求，就需要把它从路径中弹出，然后回溯到上一个位置，换一种方式继续搜索。这个过程中实际上就涉及到了“回溯”这个操作，它是回溯法的核心所在。

总的来说，回溯法更加显式地体现了搜索过程中的选择、撤销和回退，同时也更加灵活和通用，可以解决多种类型的问题。

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        ans = []
        path = []

        def is_palindrome(start, end):
            while start < end:
                if s[start] != s[end]:
                    return False
                start += 1
                end -= 1
            return True

        def dfs(start):
            if start == n:
                ans.append(path[:])
                return
            for i in range(start, n):
                if is_palindrome(start, i):
                    path.append(s[start:i + 1])
                    dfs(i + 1)
                    path.pop()

        dfs(0)
        return ans

复原 IP 地址

https://leetcode.cn/problems/restore-ip-addresses/description/

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        res = []

        def dfs(s, path):
            if len(path) == 4 and not s:
                res.append(".".join(path))
                return
            if len(path) == 4 or not s:  # 剪枝
                return
            for i in range(1, 4):
                if i <= len(s) and int(s[:i]) <= 255:
                    if i > 1 and s[0] == "0":  # 剪枝
                        break
                    dfs(s[i:], path + [s[:i]])  # ip中最多是三位数，所以i最大为3

        dfs(s, [])
        return res

回溯法：

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        res = []

        def backtrack(start, path):
            if len(path) == 4:
                if start == len(s):
                    res.append(".".join(path))
                return
            if start == len(s):
                return
            if s[start] == '0':
                backtrack(start+1, path+['0'])
            else:
                for i in range(start, min(start+3, len(s))):
                    num = int(s[start:i+1])
                    if num <= 255:
                        backtrack(i+1, path+[str(num)])
        
        backtrack(0, [])
        return res

子集

https://leetcode.cn/problems/subsets/description/

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []

        def dfs(i, tmp):
            res.append(tmp)
            for j in range(i, len(nums)):
                dfs(j + 1, tmp + [nums[j]])

        dfs(0, [])
        return res

子集 II

https://leetcode.cn/problems/subsets-ii/description/

在这个算法中，输入数组被首先排序，以使相同的元素成为相邻的，这样可以有效避免生成重复的子集。

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()

        def dfs(i, tmp):
            res.append(tmp)
            for j in range(i, len(nums)):
                if j > i and nums[j] == nums[j - 1]:
                    continue
                dfs(j + 1, tmp + [nums[j]])

        dfs(0, [])
        return res

递增子序列

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

假设现在有一个序列 nums，我们要找到所有可能的递增子序列。我们可以使用 DFS 来枚举所有可能的子序列，而且只有当子序列中包含至少两个元素时才算是有效的。

我们可以从序列的每个起始位置开始搜索，然后依次拓展序列，将所有可行的子序列加入结果集。具体来说，对于每一个起始位置，我们可以选择当前元素或者不选择当前元素。如果选择当前元素，那么只有当当前元素大于等于子序列中的最后一个元素时才能将其加入子序列。否则，我们就不选择当前元素。如果不选择当前元素，直接将子序列递归到下一层搜索即可。

有一个问题需要注意：由于题目中要求输出的递增子序列是不同的，所以我们需要在搜索过程中去重。可以使用哈希表来存储所有已经出现过的子序列，避免重复。

根据以上思路，可以得到以下代码实现：

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        res = []
        visited = set()
        
        def dfs(start, seq):
            if len(seq) > 1:
                key = tuple(seq)
                if key not in visited:
                    res.append(seq)
                    visited.add(key)
            for i in range(start, len(nums)):
                if not seq or nums[i] >= seq[-1]:
                    dfs(i + 1, seq + [nums[i]])
                    
        dfs(0, [])
        return res

全排列

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

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res=[]
        def dfs(nums,path):
            if not nums:
                res.append(path)
                return
            for i in range(len(nums)):
                dfs(nums[:i]+nums[i+1:],path+[nums[i]])
        dfs(nums,[])
        return res

全排列 II

https://leetcode.cn/problems/permutations-ii/description/

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()

        def dfs(nums, path):
            if not nums:
                res.append(path)
                return
            for i in range(len(nums)):
                if i > 0 and nums[i] == nums[i - 1]:
                    continue
                dfs(nums[:i] + nums[i + 1:], path + [nums[i]])

        dfs(nums, [])
        return res

重新安排行程

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

hard难度。

解题思路：

可以把题目转化为求欧拉通路的问题： 对于有向连通图 G，若从顶点 u 到顶点 v 存在一条路劲，则称该图为具有欧拉通路的图。

欧拉通路是指：从图的任意一点出发，不重复地经过所有边恰好一次，并回到原点的路线。

由于本题保证了所有机票至少存在一种合理的行程，且所有的机票必须都用一次且只能用一次，故该图是连通的，接下来只需要考虑如何求出欧拉通路的具体实现。

对于有向连通图 G，若存在一个顶点 v，它的入度和出度满足 in(v)−out(v)=1in(v)−out(v)=1，那么必定存在一个欧拉通路，该欧拉通路的起点是合法的终点。

若不存在这样的顶点，并且图中包含所有边，那么所有的顶点的入度和出度均相同，且存在欧拉回路（即欧拉起点和终点相同）。

在本题中，因为每个顶点都至少有一条出边，因此第一种情况是不存在的。

根据欧拉通路的算法，从起点顺着欧拉通路继续走，当走到没有出度的节点时，栈中记录的节点就是以该节点为终点的欧拉通路的前半段。

在这里采用 Hierholzer 算法来解决，Hierholzer 算法本身不用对边进行排序即可达到和深度优先搜索相同的效果，时间复杂度为 O(E)O(E)。

具体实现：

由于需要对图进行 DFS 遍历，因此可以先用邻接表预处理出整个图的信息。

再从起点（JFK）开始枚举所有的出边，递归遍历其所指向的节点。

对于递归到的每个节点，需要将对应的边从邻接表中删除（即标记已使用），以实现边只可以使用一次的效果。

在递归的过程中，顺序记录遍历的路径，当无法再扩展到更多的可达节点时，该路径即为欧拉通路的前半段。此时，从该路径的终点开始，反着遍历该路径之前经过的节点（即栈中记录的所有节点），以获得欧拉通路的后半段。

在代码实现中，可以使用 DFS+栈 的方式更新遍历路径，最终将得到起点为 JFK 的欧拉通路。

时间复杂度： O(E)O(E) ，其中 EE 为航线数组的长度。

空间复杂度： O(E)O(E) ，其中 EE 为航线数组的长度，邻接表使用的空间为 O(E)O(E)。

代码实现：

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        from collections import defaultdict
        # 构建邻接表
        graph = defaultdict(list)
        for u, v in tickets:
            graph[u].append(v)
        # 按字典序排序邻接表
        for u in graph:
            graph[u].sort()

        path = []
        stack = ["JFK"]
        while stack:
            while graph[stack[-1]]:
                # 递归遍历直到无路可走
                stack.append(graph[stack[-1]].pop(0))
            # 记录路径
            path.append(stack.pop())
        return path[::-1]

N 皇后

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

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

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

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

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

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        res = []
        def dfs(n, row, path, res):
            if row == n:
                res.append(path)
                return
            for i in range(n):
                if not isValid(path, row, i):
                    continue
                temp = '.' * n
                dfs(n, row+1, path + [temp[:i] + 'Q' + temp[i+1:]], res)
        def isValid(path, row, col):
            for i in range(row):
                if path[i][col] == 'Q' or abs(row-i) == abs(col-path[i].index('Q')):
                    return False
            return True
        dfs(n, 0, [], res)
        return res

解数独

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

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

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

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

程序的主要函数是“solveSudoku”。它将“board”列表作为参数，并使用“dfs”函数来求解数独。dfs函数的作用是填写每个未填充的空格，并检查每行、每列和每个3x3网格是否满足1-9数字的填写要求。

如果当前格子的值不是“.”，则继续搜索下一个格子。如果当前行、列或3x3网格存在数字冲突，则尝试下一个数字。如果所有数字都被尝试过并且不能填写当前的格子，则回溯到之前的状态，将前一个格子重置为“.”，并尝试一个新的数字。如果最后填充了每个格子，则返回True，否则返回False。

此外，“isValid”函数用于检查每行、每列和每个3x3网格是否有重复数字，如果有重复则返回False。如果没有重复，则返回True。

最后，该程序通过调用“dfs”函数来找到解决方案，并在“board”列表中修改每个格子的值。

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        def dfs(board, row, col):
            if col == 9:
                return dfs(board, row + 1, 0)
            if row == 9:
                return True
            if board[row][col] != '.':
                return dfs(board, row, col + 1)
            for i in range(1, 10):
                if not isValid(board, row, col, str(i)):
                    continue
                board[row][col] = str(i)
                if dfs(board, row, col + 1):
                    return True
                board[row][col] = '.'
            return False

        def isValid(board, row, col, c):
            for i in range(9):
                if board[i][col] == c:
                    return False
                if board[row][i] == c:
                    return False
                if board[(row // 3) * 3 + i // 3][(col // 3) * 3 + i % 3] == c:
                    return False
            return True

        dfs(board, 0, 0)