<jupyter_start><jupyter_text>DFS深度搜索的程序模版：```pythondef func():    res=list()        def dfs(idx, path):        '''        dfs函数，因为是闭包，可以直接访问外部res        :param idx: 对于全局来说，dfs所在的位置        :param path: 目前为止dfs已探索的路径        :return:        '''        if cond:     探索到尽头或者满足条件时返回            return                 pass        dfs(idx + 1, path + something)     若path是地址引用，需要改成path[:]        pass    init_path = None   初始探索路径，一般为0，空字串或空列表    dfs(0, init_path)    return res```个人习惯把```dfs(idx, path)```写在外部函数中构成闭包，这样做的好处是可以减少```dfs```函数的参数量。需要注意的有两点：- 如果要在```dfs```函数中修改```res```的话，```res```必须是一个地址引用，如```list```；- 若```path```是一个地址引用，在递归调用```dfs```时需要传入一个副本```path[:]```。 [Subsets II](https://leetcode.com/problems/subsets-ii/)。给定一可能有重复元素的数组，求其所有子集。思路：可能存在重复元素，那么关键就在于避免重复组合。将数组排序后，每次可判断当前新加入的数字是否与上轮数字相同，相同则跳过即可。<jupyter_code>def subsetsWithDup(nums):
    res = list()
    nums.sort()
    n = len(nums)

    def dfs(idx, path):
        res.append(path)
        if idx == n:
            return

        for i in range(idx, n):
            if i > idx and nums[i] == nums[i-1]:
                continue
            else:
                dfs(i+1, path+[nums[i]])

    dfs(0, list())
    return res<jupyter_output><empty_output><jupyter_text>[Combination Sum](https://leetcode.com/problems/combination-sum/)。给一组候选正数和一个目标值，数字可重复使用，求所有求和等于目标值的配置。思路：典型的DFS题。<jupyter_code>def combinationSum(candidates, target: int):
    candidates.sort()
    res = list()
    n = len(candidates)

    def dfs(idx, path):
        if sum(path) == target:
            res.append(path)
            return

        for i in range(idx, n):
            if sum(path)+candidates[i] <= target:
                dfs(i, path+[candidates[i]])
            else:
                return

    dfs(0, list())
    return res<jupyter_output><empty_output><jupyter_text>[Combination Sum II](https://leetcode.com/problems/combination-sum-ii/)。给一组候选正数和一个目标值，数字不可重复使用，求所有求和等于目标值的配置。思路：典型的DFS题。需要注意的是在DFS的循环中跳过重复数字。<jupyter_code>def combinationSum2(candidates, target: int):
    candidates.sort()
    n = len(candidates)
    res = list()

    def dfs(idx, path):
        if sum(path) == target:
            res.append(path)
            return

        for i in range(idx, n):
            if i > idx and candidates[i] == candidates[i-1]:
                continue
            elif sum(path)+candidates[i] <= target:
                dfs(i+1, path+[candidates[i]])
            else:
                return

    dfs(0, list())
    return res<jupyter_output><empty_output><jupyter_text>[Combination Sum III](https://leetcode.com/problems/combination-sum-iii/)。给定$[1,9]$的数字，不放回地取出$k$个数使其加和等于$n$，求所有可能的配置。思路：<jupyter_code>def combinationSum3(k: int, n: int):
    res = list()

    def dfs(idx, path):
        if len(path) == k and sum(path) == n:
            res.append(path)
            return

        for i in range(idx, 10):
            dfs(i+1, path+[i])

    dfs(1, list())
    return res<jupyter_output><empty_output><jupyter_text>[Increasing Subsequences](https://leetcode.com/problems/increasing-subsequences/)。给一数组，求出所有可能的递增子序列，序列长度至少为$2$。思路：从左往右DFS，难点在于重复值的处理。在每一个dfs函数中，维护一个集合记录已经出现过的数字，跳过重复数字。<jupyter_code>def findSubsequences(nums):
    res = list()
    n = len(nums)

    def dfs(idx, path):
        if len(path) > 1:
            res.append(path)
        if idx == n:
            return

        seen = set()
        for i in range(idx, n):
            if nums[i] in seen:
                continue

            seen.add(nums[i])
            if not path or nums[i] >= path[-1]:
                dfs(i+1, path+[nums[i]])

    dfs(0, list())
    return res<jupyter_output><empty_output><jupyter_text>[Word Search](https://leetcode.com/problems/word-search/)。在一个字符矩阵中搜索指定字串。思路：首先将问题抽象成DFS模版。在矩阵中搜索，那么```idx```肯定是一个坐标二元组。```path```是已经成功探索的路径，这里就是已匹配成功的字串长度。当```path```等于字串长度时就返回True，否则返回False。为了避免重复访问，在递归调用```dfs```时将已匹配的位置设成特殊字符。<jupyter_code>def exist(board, word: str) -> bool:
    n = len(word)
    rows, cols = len(board), len(board[0])

    def dfs(row, col, path):
        if path == n:
            return True
        if row < 0 or row >= rows or col < 0 or col >= cols or board[row][col] != word[path]:
            return False

        tmp = board[row][col]
        board[row][col] = '#'    # 避免重复访问
        res = dfs(row+1, col, path+1) or dfs(row-1, col, path+1) \
            or dfs(row, col+1, path+1) or dfs(row, col-1, path+1)
        board[row][col] = tmp

        return res

    for row in range(rows):
        for col in range(cols):
            if dfs(row, col, 0):
                return True

    return False<jupyter_output><empty_output><jupyter_text>[N-Queens II](https://leetcode.com/problems/n-queens-ii/)，猿辅导2019手撕代码题。求N皇后问题的解的数量。思路：因为每一行与每一列都只能摆一个皇后，所以可以用一个长度为$N$的数组记录皇后的纵坐标即可，一个皇后的坐标由$(i,\ arr[i])$表示。然后就是暴力破解，能摆放皇后需要满足两个条件，既不同行也不同列，左上与右上都没有皇后。<jupyter_code>def totalNQueens(n: int) -> int:
    col_idxs = [-1]*n
    res = 0

    def isValid(row, col):
        '''
        判断左上与右上是否有皇后
        '''
        left = right = col
        for i in range(row-1, -1, -1):
            if left-1 >= 0:
                left -= 1
                if col_idxs[i] == left:
                    return False
            if right+1 < n:
                right += 1
                if col_idxs[i] == right:
                    return False
        return True

    def dfs(idx):
        '''
        idx为行号
        '''
        nonlocal res
        if idx == n:
            res += 1
            return

        for col in range(n):
            if col not in col_idxs and isValid(idx, col):
                col_idxs[idx] = col
                dfs(idx+1)
                col_idxs[idx] = -1

    dfs(0)
    return res<jupyter_output><empty_output><jupyter_text>树形DFS [Binary Tree Paths](https://leetcode.com/problems/binary-tree-paths/)。给一个二叉树，返回所有根节点到叶节点的路径。每一条路径以$node.val->node.val->...$的形式返回。思路：<jupyter_code>def binaryTreePaths(self, root: TreeNode) -> List[str]:
    res = list()
    if not root:
        return res

    def dfs(idx, path):
        if not idx.left and not idx.right:
            res.append(path+[idx.val])
            return

        if idx.left:
            dfs(idx.left, path+[idx.val])
        if idx.right:
            dfs(idx.right, path+[idx.val])

    dfs(root, list())
    return ['->'.join(map(str, ans)) for ans in res]<jupyter_output><empty_output><jupyter_text>[Path Sum II](https://leetcode.com/problems/path-sum-ii/)。给一二叉树与一个目标值，求所有从根节点到叶节点求和等于$target$的路径。思路：DFS。<jupyter_code>def pathSum(root: TreeNode, target: int):
    if not root:
        return None
    res = list()

    def dfs(idx, path):
        if not idx.left and not idx.right:
            if sum(path)+idx.val == target:
                res.append(path+[idx.val])
            return

        if idx.left:
            dfs(idx.left, path+[idx.val])
        if idx.right:
            dfs(idx.right, path+[idx.val])

    dfs(root, list())
    return res<jupyter_output><empty_output><jupyter_text>[Path Sum III](https://leetcode.com/problems/path-sum-iii/)。给一二叉树和一个目标值$sum$，求该二叉树中有多少条自顶向下的路径满足其和等于目标值。思路：对于特定起点的合法路径，可以转化成[Path Sum II](https://leetcode.com/problems/path-sum-ii/)来做。这里需要求所有起点的合法路径，那么遍历一遍树，对每一个起点都应用DFS即可。<jupyter_code>def pathSum(root: TreeNode, sum: int) -> int:
    if not root:
        return 0

    def dfs(idx, path):
        res = 0
        if path+idx.val == sum:
            res += 1

        if idx.left:
            res += dfs(idx.left, path+idx.val)
        if idx.right:
            res += dfs(idx.right, path+idx.val)

        return res

    return dfs(root, 0)+pathSum(root.left, sum)+pathSum(root.right, sum)<jupyter_output><empty_output><jupyter_text>[Sum Root to Leaf Numbers](https://leetcode.com/problems/sum-root-to-leaf-numbers/)。给一颗二叉树，根节点到叶节点路径上的所有数字拼接起来构成一个大数，求所有路径构成数字的总和。思路：DFS。每深入一层，已有答案需要乘$10$后再加上节点值。<jupyter_code>def sumNumbers(root: TreeNode) -> int:
    res = 0
    if not root:
        return res

    def dfs(idx, path):
        nonlocal res
        if not idx.left and not idx.right:
            res += path
            return

        if idx.left:
            dfs(idx.left, path*10+idx.left.val)
        if idx.right:
            dfs(idx.right, path*10+idx.right.val)

    dfs(root, root.val)
    return res<jupyter_output><empty_output><jupyter_text>[Smallest String Starting From Leaf](https://leetcode.com/problems/smallest-string-starting-from-leaf/)。给一颗二叉树，节点值的范围为$[0,25]$，代表$[a,z]$。求一条从叶结点到根节点且字典序最小的路径。规定在同样前缀的情况下，字符越短字典序越小。思路：DFS。路径由叶节点到根节点，那么路径字串的首字符由叶节点决定，所以在走到叶节点之前是无法确定字典序的。每当DFS走到叶节点，比较已有结果与当前路径的字典序。<jupyter_code>def smallestFromLeaf(self, root: TreeNode) -> str:
    if not root:
        return None

    res='{'

    def dfs(idx,path):
        nonlocal res
        path.append(chr(idx.val+97))
        if not idx.left and not idx.right:
            res=min(res,''.join(reversed(path)))

        if idx.left:
            dfs(idx.left,path)
        if idx.right:
            dfs(idx.right,path)
        path.pop()

    dfs(root,list())
    return res<jupyter_output><empty_output><jupyter_text>BFSBFS同DFS，模版几乎相同，不过遍历的方法稍微有区别。某些场景下个人更熟悉使用队列实现BFS。 [Friend Circles](https://leetcode.com/problems/friend-circles/)。给一无向图的邻接矩阵，求联通分量数。思路：无向图的BFS，使用队列实现，需要维护一个访问状态。<jupyter_code>def findCircleNum(M) -> int:
    n = len(M)
    visited = [False]*n
    q = list()
    res = 0

    for idx in range(n):
        if not visited[idx]:
            res += 1
            q.append(idx)

            while q:
                vis_node = q.pop()
                visited[vis_node] = True

                for node_idx in range(n):
                    if not visited[node_idx] and M[vis_node][node_idx]:    # 未访问的邻居
                        q.append(node_idx)

    return res<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.14022064130322714, 'fraction_numerical': 0.00732034230333024, 'mean_word_length': 2.415492957746479, 'pattern_counts': {'":': 0, '<': 58, '<?xml version=': 0, '>': 70, 'https://': 14, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '13', 'dir': 'jupyter-structured-clean-dedup', 'id': '410900', 'license': 'MIT', 'n_tokens_mistral': 4292, 'n_tokens_neox': 4408, 'n_words': 607, 'path': 'Algorithm/BlankBoard/.ipynb_checkpoints/DFS&BFS-checkpoint.ipynb', 'repo_name': 'Daya-Jin/DataStructureAndAlgorithm', 'size': '9699'}