回溯.md

回溯算法相关

观点：深度优先遍历，递归，栈三者的关系，背后的统一逻辑都是【后进先出】

1. 回溯法：

   • 采用试错的思想，分步解决一个问题
   • 当现有分布答案不能解决问题时，则取消上一步甚至上几步的计算，再通过其他的，可能的分步解答尝试其他答案
   • 常使用递归
   • 重复计算的结果是：
     • 找到一个可能存在的答案
     • 尝试所有组合或可能后发现没有答案

2. 深度优先搜索

   • 用于便利或者搜索树（图）的算法，尽可能深的搜索树的分支
   • 当节点v的所在边都已经被探寻过，搜索将回溯到发现结点 v 的那条边的起始结点。直到访问完所有节点

3. 二者联系：

   • 【回溯算法】强调了【深度优先遍历】思想的用途，用一个 不断变化 的变量，在尝试各种可能的过程中，搜索需要的结果。强调了 回退 操作对于搜索的合理性。
   • 【深度优先遍历】强调一种遍历的思想
   • 搜索和遍历的区别：
     • 搜索问题的解，可以通过 遍历 实现。
     • 回溯算法用于 搜索一个问题的所有的解 ，通过深度优先遍历的思想实现。
   • 【回溯】与【动态规划】的区别：
     • 共同点：求解多阶段决策问题
       • 求解一个问题分为很多步骤（阶段）
       • 每一个步骤（阶段）可以有多种选择
     • 不同点：
       • 【动态规划】只需要求我们评估最优解是多少，对应的具体解不要求，用于评估方案效果
       • 回溯算法可以搜索得到所有的方案（当然包括最优解），本质上是遍历，时间复杂度很高。

4. 搜索的方法：

   • 按顺序枚举每一位可能出现的情况，已经选择的数字在 当前 要选择的数字中不能出现。按照这种策略搜索就能够做到 不重不漏。

5. 逻辑：

   • 状态：变量的不同值
   • 状态重置：状态变量需要设置为和先前一样，也就是撤回上一次的选择
   • 深度优先遍历：往下走时在路径path变量尾部添加，撤销时在path变量尾部撤销，path变量就是栈。【深度优先遍历】通过【回溯】操作，实现了全局使用一份状态变量的效果
   • 从树的根节点到叶子结点形成的路径就是其中一个全排列

6. 设计状态变量：

   • 递归结构
   • 递归终止条件，当前程序递归到第几层
   • 布尔数组，表示哪些数还没有选择过，选择过的用True，没有选择过的用False

7. 为什么不使用广度优先遍历：

   • 深度优先遍历中每两个状态之间只相差一个位置的变化，退回比较容易；但是广度优先由浅层转到深层状态变化比较大；
   • 深度优先直接使用系统栈，而广度优先遍历则需要使用队列，存储每一步的状态信息，可能会产生很大的冗余

8. 剪枝

   • 回溯算法会应用「剪枝」技巧达到以加快搜索速度。有些时候，需要做一些预处理工作（例如排序）才能达到剪枝的目的。预处理工作虽然也消耗时间，但能够剪枝节约的时间更多；

广度优先遍历

1. 寻找最短路径的问题

46，全排列，中等

核心方法：回溯

难点：

1. 需要传入深度优先遍历的参数
   • 不变的参数：数组本身，数组长度
   • 变化的参数：每次的排列path，存储排列的结果res，递归到的层数depth，还可以选择的元素数组used
2. 存储结果时，需要将排列结果拷贝一份，再加入结果中；这里使用path[:]，因为原始列表的变量名只是提供了一个指向列表的指针，如果直接使用res.append(path)，那么传入的只是这个指针，会随着path变化而变化，最后的结果会是6个空列表（由于path最终会回到初始值[]），而不是排列。
3. 复杂度分析
   • 时间复杂度：O(N×N!)
   • 空间复杂度：O(N×N!)
     • 递归树深度 logN；
     • 全排列个数 N!，每个全排列占空间 N。取较大者。

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def dfs(nums, n, depth, path, used, res):
            if depth == n:
                res.append(path[:])
			# 开始遍历整个数组
            for i in range(n):
                # 如果当前遍历到的元素没有被使用，那么就可以被使用
                if not used[i]:
                    used[i] = True
                    path.append(nums[i])
					# 开始递归
                    dfs(nums, n, depth+1, path, used, res)
					# 开始回溯，对当前位置的值进行撤回，使用状态恢复为未使用
                    used[i] = False
                    path.pop()
                    
        def dfs1(path, depth):
            # 这个方法占用的空间比较大，耗时比较多
            # 创建很多中间变量，这些中间变量有些是不需要的
            if depth == n:
                res.append(path)
                return res
            for i in range(n):
                if not used[i]:
                    used[i] = 1
                    dfs(path + [nums[i]], depth+1)
                    used[i] = 0

        n = len(nums)
        if n == 0: return []
        
        used = [False for _ in range(n)]
        res = list()
        # 开始进行树的搜索
        dfs(nums, n, 0, [], used, res)
        return res

22，括号生成，中等

此题已经记录过了，可以参考之前【数组】代码

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        # 哪些还没有选择过，使用L和R表示左右括号剩余可用的个数
        def dfs(cur_str, L, R):
            if L == 0 and R == 0:
                # 递归终止条件
                res.append(cur_str)
                return 
            if right < left:
                # 剪枝，代表递归结束，右括号的数量一定是大于左括号的
                return 
            if L > 0:
                # 如果左括号还有，则继续添加，右括号情况相同
                dfs(cur_str + '(', L-1, R)
            if R > 0:
                dfs(cur_str + ')', L, R-1)
        
        res = []
        dfs('', n, n)
        return res

剑指offer38，字符串的排列，中等

核心方法：回溯

难点：如果原始字符串中包含重复字符，需要在每层循环开始之前设置一个集合，因为每次开始新的一轮回溯，相当于是获取一个新位置的值；那么加在每层循环前的集合，就是针对这个位置进行去重的。也就是说，如果这个位置已经存在了相同的值，那么直接跳到下一个元素。这样比较有效

• 时间复杂度：时间复杂度 $O(N!N)$ ： N 为字符串 s 的长度；时间复杂度和字符串排列的方案数成线性关系，方案数为 $N \times (N-1) \times (N-2) … \times 2 \times 1$ ，即复杂度为 $O(N!)$ 。

• 空间复杂度 $O(N^2)$ ： 全排列的递归深度为 $N$ ，系统累计使用栈空间大小为 $O(N)$ ；递归中辅助 Set 累计存储的字符数量最多为 $N + (N-1) + ... + 2 + 1 = (N+1)N/2$ ，即占用 $O(N^2)$ 的额外空间。

class Solution:
    def permutation(self, s: str) -> List[str]:
        self.res = []
        self.ans = ''
        n = len(s)

        def backtrack(s):
            if len(self.ans) == n:
                self.res.append(str(self.ans))
                return
            dic = set()  # 设立哨兵集合来阻挡重复进入
            for i in range(0,len(s)):
                if s[i] in dic: continue  # 重复则略过此次循环，称为剪枝
                dic.add(s[i])  # 记得不在的时候需要放入set
                self.ans += s[i]
                backtrack(s[:i] + s[i+1:])  # 排除掉当前的i，将s中剩余的字符串再进行回溯
                self.ans = self.ans[:-1]
        backtrack(s)
        return list(self.res)

10，正则表达式匹配，困难

核心方法：回溯

难点：查找s和p的每个位置是否匹配

• 如果只有'.'的情况，我们需要从左到右依次判断s[i]和p[i]是否匹配
• 如果有'*'，会出现在p[1]的位置
  • 如果匹配0个，那么忽略'*'以及前面的字符，继续比较下一个
  • 如果匹配一个或多个，那么忽略掉s中的第一个元素，继续比较下一个

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        # 终止条件：如果p为空，如果s为空则为True（两个都查找完了）
        # 如果s不为空，则为False，表示不能匹配上，因为s还有剩余
        if not p: return not s
        # 第一个字母是否匹配
        # 即判断s是否有剩余，p[0]是否等于s[0]或者'.'
        first_match = bool(s and p[0] in {s[0],'.'})
        # 如果 p 第二个字母是 *
        if len(p) >= 2 and p[1] == "*":
            # self.isMatch(s, p[2:]) 表示忽略掉p中的前两个，这时可以不考虑第一个位置是否匹配，因为即使第一个位置没有匹配到，p[:2]匹配的也是0个
            # 或者 first_match 为 True
            return self.isMatch(s, p[2:]) or first_match and self.isMatch(s[1:], p)
        else:
            return first_match and self.isMatch(s[1:], p[1:])

核心方法：动态规划（推荐）

难点：dp[i][j] 表示的状态是 s 的前 i 项和 p 的前 j 项是否匹配。

已知了 dp[i-1][j-1] 的状态，分三种情况确定 dp[i][j] 的状态

• s[i] == p[j] or p[j] == '.'时dp[i][j] = dp[i-1][j-1] = True
• p[j] == '*'，星号与前面的字符相关，比较星号前面的字符 p[j-1] 和 s[i] 的关系。
  • p[j-1] != s[i]：如果星号前一个字符匹配不上，星号匹配了 0 次。应忽略这两个字符，看 p[j-2] 和 s[i] 是否匹配。 这时 dp[i][j] = dp[i][j-2]。
  • p[j-1] == s[i] or p[j-1] == '.'：星号前面的字符可以与 s[i] 匹配，这种情况下，星号可能匹配了前面的字符的 0 个，也可能匹配了前面字符的多个。当匹配 0 个时，这时我们需要去掉 p 中的 b* 或 .* 后进行比较，即 dp[i][j] = dp[i][j-2]；当匹配多个时，我们需要将 s[i] 前面的与 p 重新比较，即 dp[i][j] = dp[i-1][j]
• 其他情况为不匹配，即 dp[i][j] = False

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        # 边界条件，考虑 s 或 p 分别为空的情况
        if not p: return not s
        if not s and len(p) == 1: return False
		
        m, n = len(s) + 1, len(p) + 1
        # 所有初始状态全部设置为 False
        dp = [[False for _ in range(n)] for _ in range(m)]
        # 初始状态
        dp[0][0] = True
        dp[0][1] = False
		
        # 当 s 为空字符串时，p字符串能否与之匹配需要分情况讨论
        # 如果s为空，p等于'a*'时，那么s与p是匹配的，此时 dp[0][2] = dp[0][0]
        # 缺少的2就是'a*'的长度2
        for c in range(2, n):
            # 在这个循环中n是取不到的，当时由于n = len(p) + 1，c 可以取到p的最后一个字符
            # 实际在状态转移的过程中，如果已经确定[j]的情况了，那么之后只需要关注[j+1]的情况
            # 所以这里和后面都使用了相同的处理方法：j = c - 1 和 i = r - 1
            j = c - 1  # 判断时使用j，使用c进行状态转移
            if p[j] == '*':
                dp[0][c] = dp[0][c - 2]
        
        # r, c都是从1的位置开始进行状态转移的，因为0的位置是初始化时完成的
        # 但是
        for r in range(1,m):
            i = r - 1
            for c in range(1, n):
                j = c - 1
                if s[i] == p[j] or p[j] == '.':
                    dp[r][c] = dp[r - 1][c - 1]
                elif p[j] == '*':       # ‘*’前面的字符匹配s[i] 或者为'.'
                    if p[j - 1] == s[i] or p[j - 1] == '.':
                        dp[r][c] = dp[r - 1][c] or dp[r][c - 2]
                    else:                       # ‘*’匹配了0次前面的字符
                        dp[r][c] = dp[r][c - 2] 
        return dp[m - 1][n - 1]

131，分割回文串，中等

核心方法：回溯+动态规划

难点：这里i选择从后向前进行遍历，是原因的。如果从前向后进行遍历，且我们知道，dp[i][j]是依赖于dp[i+1][j-1]，这时s[i+1]可能还未遍历到，初始值并不一定就是动态规划结束后的值，而从后往前遍历就没有这个问题

• 时间复杂度：$O(n \cdot 2^n)$，其中 n 是字符串 s 的长度。在最坏情况下，s 包含 n 个完全相同的字符，因此它的任意一种划分方法都满足要求。而长度为 n 的字符串的划分方案数为 $2^{n-1}=O(2^n)$，每一种划分方法需要 $O(n)$ 的时间求出对应的划分结果并放入答案，因此总时间复杂度为 $O(n \cdot 2^n)$。
• 空间复杂度：数组 f 需要使用的空间为 $O(n^2)$

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        # 采用回溯 + 动态规划预处理
        n = len(s)
        dp = [[True] * n for _ in range(n)]
        
        # 使用动态规划首先将所有s的所有子串全部预处理出来
        for i in range(n-1, -1, -1):
            for j in range(i+1, n):
                # s[i..j]是回文串的条件：头尾字符相等，且s[i+1..j-1]是回文串
                # 或者 i >= j: 也就是同一个字符，或者是空串，所以这里的j从i+1开始
                dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]

        res = list()
        ans = list()

        # 深度优先遍历
        def dfs(i):
            # 终止条件：当起始值i等于终点值n，表示遍历完毕
            if i == n:
                res.append(ans[:])
                return 
            
            for j in range(i, n):
                if dp[i][j]:
                    ans.append(s[i:j+1])
                    dfs(j+1)  # 下一个位置进行递归
                    ans.pop()
        dfs(0)
        return res

93，复原IP地址，中等

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        def isValid(s, start, end):
            """传入：字符串s，开始处理s的起始位置，字符串s末尾索引"""
            if start > end:
                # 如果已经超出去了，就返回无效
                return False
            if s[start] == '0' and start != end:
                # 如果第一位是0，而且这个IP段长度大于1，返回无效
                # start != end 表示这一个IP段的长度已经大于1了，此时的s是添加"."后的结果，
                # end表示s末尾索引，如果start表示第4个IP段的第一个字符索引
                # 如果有效，那么s[start]==0时，start = end，否则无效
                return False
            num = 0
            for i in range(start, end + 1):
                if s[i] > '9' or s[i] < '0':
                    # 字符如果大于9或者小于0，返回无效
                    return False
                num = num*10 + (int(s[i]) - 0)
                if num > 255:
                    # 转为int型后，如果超出边界，则无效
                    return False
            # 都不满足，则返回有效
            return True

        def backtracking(s, startindex, pointnum):
            """
            传入【字符串s，起始位置，"."的个数】
            """r
            if pointnum == 3:
                # 在字符串中插入了3个"."时，说明已将s划分完成，此时进行有效性判断
                if isValid(s, startindex, len(s)-1):
                    # 如果返回有效，则将结果添加到res中
                    res.append(s)
                return  # 剪枝
            for i in range(startindex, len(s)):
                # 此处i为s的所有索引
                if isValid(s, startindex, i):
                    # 这里的有效性判断，主要是为了验证已划分出来的，最右边的区间是否有效
                    # 这里相当于添加并移动了“.”的位置在整个s中
                    s = s[:i+1] + '.' + s[i+1:]
                    pointnum += 1
                    backtracking(s, i+2, pointnum)  # 这里+2是由于中间插入了一个"."
                    # 这里传入的i+2作为下一次的startindex，表示的是下一个待处理的字符
                    pointnum -= 1  # 不满足这个条件时，pointnum-1表示去掉上一个区间的划分
                    # 去掉上一个添加的"."，接下来重新进行循环，重新分配"."的位置
                    s = s[:i+1] + s[i+2:]  
                else:
                    break
        
        # 如果字符串长度大于12，则直接返回空
        if len(s) > 12:
            return []
        res = list()
        # 下面的0，表示每个IP字段（长度为3）中当前指向的位置，在0，1，2三个数当中的一个
        backtracking(s, 0, 0)
        return res

79，单词搜索，中等

核心方法：回溯，函数check(i,j,k)判断从网格的(i,j)位置出发，能否搜索到单词word[k..]，word[k..]表示word中从位置k开始的子串

复杂度分析：

• 时间复杂度：在每次调用函数 $\text{check}$ 时，除了第一次可以进入 4 个分支以外，其余时间我们最多会进入 3 个分支。由于单词长为 L，故 $\text{check(i, j, 0)}$ 的时间复杂度为 $O(3^L)$，而我们要执行 $O(MN)$ 次检查，其中 M,N 为网格的长度与宽度。一个非常宽松的上界为 $O(MN \cdot 3^L)$
• 空间复杂度：$O(MN)$。我们额外开辟了 $O(MN)$ 的 $\textit{visited}$数组，同时栈的深度最大为 $O(\min(L, MN))$。

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        # 对于每个位置，只有上下左右四个方向可以移动，这里的元组表示的是移动的方向
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        def check(i: int, j: int, k: int) -> bool:
            if board[i][j] != word[k]:
                # 当前位置上已经不匹配了，就返回 False
                return False
            if k == len(word) - 1:
                # 能够遍历到字符串的末尾，就返回 True
                return True
            
            visited.add((i, j))  # 访问过的位置要添加
            result = False
            for di, dj in directions:
                # 从四个方向中依次选取并改变新位置
                newi, newj = i + di, j + dj
                if 0 <= newi < len(board) and 0 <= newj < len(board[0]):
                    # 需要保证边界没有超出
                    if (newi, newj) not in visited:
                        # 剪枝，访问过的位置就不能再访问了
                        if check(newi, newj, k + 1):
                            result = True
                            break
            
            visited.remove((i, j))  # 退出这一轮添加的位置
            return result

        h, w = len(board), len(board[0])
        visited = set()
        # 将每一个位置作为初始值，进行 check(i, j, 0) 检查，有一个能匹配上就返回 True
        for i in range(h):
            for j in range(w):
                if check(i, j, 0):
                    return True
        
        return False

17，电话号码的字母组合，中等

核心方法：回溯。回溯的循环部分为：维护一个字符串，表示已有的字母排列，该字符串初始为空。每次取电话号码的一位数字，从哈希表中获得该数字对应的所有可能的字母，并将其中的一个字母插入到已有的字母排列后面，然后继续处理电话号码的后一位数字

时间复杂度：$O(3^m \times 4^n)$，其中 m 是输入中对应 3 个字母的数字个数（包括数字 2、3、4、5、6、8），n 是输入中对应 4 个字母的数字个数（包括数字 7、9），$m+n$ 是输入数字的总个数。

空间复杂度：$O(m+n)$，空间复杂度主要取决于哈希表以及回溯过程中的递归调用层数，哈希表的大小与输入无关，可以看成常数，递归调用层数最大为 m+n。

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))
            else:
                digit = digits[index]
                for letter in phoneMap[digit]:
                    # 每次从一个数字对应的字母中获取一个，然后移动到下一个数字
                    combination.append(letter)
                    backtrack(index + 1)
                    combination.pop()

        combination = list()  # 存放每一种字母的组合
        combinations = list()
        backtrack(0)
        return combinations

78，子集，中等

核心方法：回溯

难点：区别于之前的几个题目，这个题目没有终止条件，因为需要寻找子集，每个子集的长度也没有规定，因此只要递归一次，就保留一次的结果。

时间复杂度：$\textit{nums}$ 中枚举其所有 $2^n$ 个子集，每个子集加入答案时需要拷贝一份，耗时 $O(n)$。那么最终的时间复杂度为$O(n \times 2^n)$

空间复杂度：使用栈，栈的最长度为n，所以O(n)

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def dfs(idx, tmp):
            # 没有终止条件，每次回溯时直接将上一轮tmp结果赋给res就行
            res.append(tmp[:])
            # 回溯循环：
            for i in range(idx, len(nums)):
                tmp.append(nums[i])
                dfs(i+1, tmp)
                tmp.pop()

        res = []
        dfs(0, [])
        return res

90，子集2，中等

核心方法：回溯。与上一题不同是，解集中不能出现重复的子集。所以在出现重复元素时，应当通过索引平移的方式跳过相同的元素。另外，为了保证上述操作能够通过，还需要对原始数组进行排序。其余结构与上一个代码相同

时间复杂度：排序的时间复杂度为 $O(n \log n)$。最坏情况下 $\textit{nums}$ 中无重复元素，需要枚举其所有 $2^n$ 个子集，每个子集加入答案时需要拷贝一份，耗时 $O(n)$。那么最终的时间复杂度为$O(n \times 2^n)$

空间复杂度：使用栈，栈的最长度为n，所以O(n)

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        def dfs(idx, tmp):
            res.append(tmp[:])
            for i in range(idx, len(nums)):
                # 出现重复元素时，应当通过索引平移的方式跳过相同的元素
                if i > idx and nums[i] == nums[i-1]:
                    continue
                tmp.append(nums[i])
                dfs(i+1, tmp)        
                tmp.pop()

        res = list()
        nums.sort()  # 对原数组进行排序
        dfs(0, [])
        return res

39，组合总和，中等

核心方法：回溯+栈

难点：每次深度遍历时，需要判断当前组合的和是否等于target：如果等于target，那么将组合添加到结果中；如果和大于target，说明超出了，直接返回空，也就是需要弹出最后一个元素，重新选取。在for循环中，如果当前元素已经大于target了，那么直接跳出当前循环。

时间复杂度：

空间复杂度：使用栈空间，最长为 $O(n)$

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        if min(candidates) > target: return []
        candidates.sort() 
        res = list()

        def dfs(idx, tmp, target):
            if target == 0:
                res.append(tmp[:])
            if target < 0:
                return
            for i in range(idx, len(candidates)):
                if candidates[i] > target:
                    break
                tmp.append(candidates[i])
                target -= candidates[i]
                dfs(i, tmp, target)
                tmp.pop()
                target += candidates[i]

        dfs(0, [], target)
        return res
    
# 或者使用下面这种方法
class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        if min(candidates) > target:
            return []
        candidates.sort()
        res = []

        def helper(candidates, target, temp_list):
            if target == 0:
                res.append(temp_list)
            if target < 0:
                return
            for i in range(len(candidates)):
                if candidates[i] > target:
                    break
                # 这里每次传入的是，截断后的candidates，减去新增值的target，更新后的组合
                helper(candidates[i:], target - candidates[i], temp_list + [candidates[i]])
        helper(candidates,target,[])
        return res

77，组合，中等

核心方法：回溯

难点：方法比较固定，要注意终止条件是当临时组合的元素个数等于k时，来达到的。也要注意组合中的元素和索引可以合二为一

时间复杂度：$\textit{nums}$ 中枚举其所有 $2^n$ 个子集，每个子集加入答案时需要拷贝一份，耗时 $O(n)$。那么最终的时间复杂度为$O(n \times 2^n)$

空间复杂度：使用栈，栈的最长度为n，所以O(n)

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def dfs(idx, tmp):
            if len(tmp) == k:
                res.append(tmp[:])
                return
            for i in range(idx, n+1):
                tmp.append(i)
                dfs(i+1, tmp)
                tmp.pop()

        res = list()
        dfs(1, [])
        return res

40，组合总和2，中等

核心方法：回溯+排序

难点：对于给定数组中元素有重复，且每个组合中每个元素只能使用一次的要求，一定要想到使用首先使用排序，然后在深度优先遍历的循环中，判断当前元素是否等于上一个元素，如果等于，则要跳过这个元素，再进行下一层深度回溯。

时间复杂度：排序的时间复杂度为 $O(n \log n)$。最坏情况下 $\textit{nums}$ 中无重复元素，需要枚举其所有 $2^n$ 个子集，每个子集加入答案时需要拷贝一份，耗时 $O(n)$。那么最终的时间复杂度为$O(n \times 2^n)$

空间复杂度：使用栈，栈的最长度为n，所以O(n)

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        if min(candidates) > target: return []
        candidates.sort() 
        res = list()

        def dfs(idx, tmp, target):
            if target == 0:
                res.append(tmp[:])
            if target < 0:
                return
            for i in range(idx, len(candidates)):
                if candidates[i] > target:
                    break
                if i > idx and candidates[i] == candidates[i-1]:
                    continue
                tmp.append(candidates[i])
                target -= candidates[i]
                dfs(i+1, tmp, target)
                tmp.pop()
                target += candidates[i]

        dfs(0, [], target)
        return res

51，N皇后，困难

核心方法：回溯

难点：

• 任何两个皇后都不能在同一行，同一列，或是同一条斜线上。每一行有且仅有一个皇后，每一列有且仅有一个皇后，每一条斜线上有且仅有一个皇后。
• 使用一个数组记录每行放置的皇后的列下表，依次在每行放置一个皇后。每次新放置的皇后都不能和已经放置的皇后在同一列和同一斜线上，并更新数组中当前行的皇后列下表，当N个皇后都放置完毕，则找到一个可能的解。
• 第1个皇后有n中选择，第2个皇后有n-1中选择，第3个皇后有n-2个选择，所以时间复杂度为为O(N!)
• 当找到一个可能解后，将数组转换为表示棋盘状态的列表，并将该棋盘状态的列表加入结果列表中
• 为了降低时间复杂度，每次放置皇后时需要快速判断每个位置是否可以放置皇后。最理想的情况是在O(1)时间复杂度内判断该位置所在的列和斜线上是否已经有皇后
• 使用三个集合，columns, diagonals1, disgonals2 分别记录每一列和两个方向上的每条斜线是否有皇后。列表上很直观，斜线的表示分为两种情况
  • 从左上到右下的情况，同一斜线下，行下标和列下标之差相等
  • 从右上到左下的情况，同一斜线下，行下标和列下标之和相等
  • 每次放置皇后时，对于每个位置判断其是否在三个集合中，如果三个集合都不包含当前位置，则当前位置是可以放置皇后的。
• 复杂度分析
  • 时间复杂度：O(N!)，其中 NN 是皇后数量。
  • 空间复杂度：O(N)，空间复杂度主要取决于递归调用层数、记录每行放置的皇后的列下标的数组以及三个集合，递归调用层数不会超过 N，数组的长度为 N，每个集合的元素个数都不会超过 N。

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def generateBoard():
            # 将结果转化为棋盘的形式
            board = list()
            for i in range(n):
                # 这里的queens的每一个位置都已经更新了列下标，以这个列下标为索引，将row中每行指定索引对应的数赋值为Q
                row[queens[i]] = "Q"
                board.append("".join(row))
                row[queens[i]] = "."
            return board

        def backtrack(r: int):
            # row表示行数，当遍历到最后一行时，则获得了一个解
            if r == n:
                board = generateBoard()
                solutions.append(board)
            else:
                for i in range(n):
                    # 此时的i表示这个皇后所在的列下标，要求该列下标不在列集合中，且行下标的差不在斜线集合1中，且列下标的和不在斜线集合2中
                    if i in columns or r - i in diagonal1 or r + i in diagonal2:
                        continue
                    queens[r] = i
                    columns.add(i)
                    diagonal1.add(r - i)
                    diagonal2.add(r + i)
                    backtrack(r + 1)  # 回溯传递的是每一行
                    columns.remove(i)
                    diagonal1.remove(r - i)
                    diagonal2.remove(r + i)
                    
        solutions = list()
        queens = [-1] * n  # 记录每个可以放置皇后的列下标
        columns = set()
        diagonal1 = set()
        diagonal2 = set()
        row = ["."] * n
        backtrack(0)
        return solutions

44，通配符匹配，困难

核心方法：动态规划。本题和正则表达式相比，比较相似。不同的是，正则表达式匹配的是，字符P中的通配符还需要和其前一个字符组成后再与s中的字符串进行匹配；而这里的p中的单个字符就能与s中的字符进行匹配。

难点：

• 使用 dp[i][j] 表示 s 中前i个字符能否和p中的前j个字符进行匹配
• 状态转移
  • 如果p_j是字母，那么s_i必须与p_j相等，公式为：dp[i][j] = p[j] == s[i] & dp[i-1][j-1]
  • 如果p_j是?号，那么s_i都可以，公式为：dp[i][j] = dp[i-1][j-1]
  • 如果p_j是*号，有两种情况，使用或者不使用
    • 如果使用，就是匹配多个s，那么dp[i][j] = dp[i-1][j]
    • 如果不使用，就是匹配空，那么dp[i][j] = dp[i][j-1]
  • 前两个状态转移可以进行合并，最终为：
    • dp[i][j] = dp[i-1][j-1]，当p[j]等于问号，或p[j]==s[i]
    • dp[i][j] = dp[i-1][j] or dp[i][j-1]，当p[j]等于*时
    • False，other situation
• 边界条件
  • dp[0][0]=True，两个都为空，可以匹配
  • dp[i][0]=False，p为空，一定不能匹配
  • dp[0][j] 需要分情况讨论：因为星号才能匹配空字符串，所以只有当模式 p 的前 j 个字符均为星号时，dp[0][j] 才为真
  • dp[0][j] 在 j 大于模式 p 的开头出现的星号字符个数之后，值也恒为假，而 dp[i][j] 的默认值（其它情况）也为假，因此在对动态规划的数组初始化时，我们就可以将所有的状态初始化为 False，减少状态转移的代码编写难度。
  • 最终的答案即为 dp[m][n]，其中 m 和 n 分别是字符串 s 和模式 p 的长度。
• 复杂度分析：
  • 时间复杂度：O(mn)，其中 m 和 n 分别是字符串 s 和模式 p 的长度。
  • 空间复杂度：O(mn)，即为存储所有 (m+1)(n+1) 个状态需要的空间。

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
		
        # 对所有边界条件进行初始化
        # m+1 目的是保证行能够取到 m
        # 但是 n+1 又是为什么？
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True
        # 这里不从 0 开始取 i 是因为 dp[0][0]的值已经确定了
        # n+1 是为了保证 i=n 能够取到
        for i in range(1, n + 1):
            if p[i - 1] == '*':
                dp[0][i] = True
            else:
                break
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == '*':
                    dp[i][j] = dp[i][j - 1] | dp[i - 1][j]
                elif p[j - 1] == '?' or s[i - 1] == p[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                
        return dp[m][n]

841，钥匙和房间，中等

核心方法：深度优先搜索

题目要求的是，从第0号节点出发是否能够达到所有的节点。可以使用深度优先搜索的方式遍历整张图，统计可以到达的节点个数，并利用数组vis标记当前节点是否访问过，以防止重复访问。

• 时间复杂度：O(m+n)，m表示所有房间中的钥匙数量的总数，n是房间数量
• 空间复杂度：O(n)，递归的栈空间

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        def dfs(x):
            # 将当前房间数添加到访问历史中
            vis.add(x) 
            nonlocal num  # 把变量标记为自由变量
            num += 1  # 访问过的房间数+1
            for it in rooms[x]:
                # 从当前访问的房间中选取钥匙，选择没有访问过的房间（钥匙）进行递归
                if it not in vis:
                    dfs(it)

        n = len(rooms)  # 房间总数
        num = 0  # 能够进入房间的总数
        vis = set()  # 访问过的房间
        dfs(0)  # 从第一个房间开始递归
        # 如果所有的房间都访问过了，那么访问次数应该等于房间总数
        return num == n

推荐 核心方法：广度优先搜索

使用队列先进先出的特点，依次尝试每个房间的所有钥匙，记录能够访问的房间数量

• 时间复杂度：O(m+n)
• 空间复杂度：O(n)，主要为队列的开销

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        n = len(rooms)
        num = 0
        vis = {0}
        que = collections.deque([0])

        while que:
            x = que.popleft()
            num += 1
            for it in rooms[x]:
                if it not in vis:
                    vis.add(it)
                    que.append(it)
        return num == n

967，连续差相同的数字，中等

核心方法：BFS

首先设定可选择的集合为1-9的数字，遍历N-1次，每次从这个集合中获取任意数字，判断自己的末位数字与K值的差或和是否在0-9之间； 如果满足这个条件，那么这个差或和拼接在原来的任意数字之后，就能够满足差值为K的条件。遍历N-1次后，这些值就产生了

复杂度分析

• 时间复杂度：O(2^N)O(2N)。
• 空间复杂度：O(2^N)O(2N)。

class Solution(object):
    def numsSameConsecDiff(self, N, K):
        ans = {x for x in range(1, 10)}
        for _ in range(N-1):
			# 用来记录每一轮位置遍历后满足条件的备选数
            ans2 = set()
            for x in ans:
                d = x % 10
                # 需要满足当前数x的末尾d与K的差或和是在0-9之间的
                if d - K >= 0:
                    ans2.add(10*x + d-K)  # 将新值拼接在备选数之后
                if d + K <= 9:
                    ans2.add(10*x + d+K)
            # 每个位置的值遍历完毕后需要更新下一轮的备选方案
            ans = ans2

        # 长度为1时，0也是满足条件的，需要补充进去
        if N == 1:
            ans.add(0)

        return list(ans)

下面的代码和上面的思想一样，只是在表达上更准确

class Solution:
    def cal(self, s):
        # 将s（一个数组）中的各个数组合
        res = 0
        for t in s:
            res = res * 10 + t
        return res
    
    def numsSameConsecDiff(self, n, k):
        Q = collections.deque()
        for i in range(1, 10):
            Q.append([i])
        res = []
        while Q:
            print(Q)
            v = Q.popleft()
            if len(v) == n:
                # 如果一组结果包含的数达到长度要求，那么将其合并后输入到返回结果中
                res.append(self.cal(v))
            elif k == 0:
                # 如果绝对差值为0，直接将同一个数补充进行
                v.append(v[-1])
                Q.append(v)
            else:
                if v[-1] - k >= 0:
                    # 这里注意：需要对列表进行复制
                    t = v.copy()
                    t.append(t[-1] - k)
                    Q.append(t)
                if v[-1] + k < 10:
                    t = v.copy()
                    t.append(t[-1] + k)
                    Q.append(t)
        return res

127，单词接龙，困难

核心方法：最短转换序列的长度，首先应当想到广度优先搜索，需要将其抽象为图

将每个单词都抽象为一个点，如果两个单词可以通过指改变一个字母进行转化的，说明他们之间有一条双向边，把所有满足条件的点相连，就形成一个图。基于下面这个图，我们以beginWord为起点，以endWord为终点进行BFS，寻找最短路径

算法：

1. 首先给所有wordList中的单词进行编号，创建单词与id的映射字典；然后检查endWord是否在该字典中，如果不在返回0.

2. 然后建图，常见做法为取两两单词组合，判断他们是否恰好相差一个字符，来判断两个单词之间是否相连。效率比较低，需要优化。优化方法为：创建3个虚拟节点，针对hit，创建3个虚拟节点*it， h*t， hi*，并让hit向这三个虚拟节点分别连一条边即可。如果一个单词能够转化为hit，那么这个单词必然会连接到这三个虚拟节点之一。对于每一个单词，我们枚举它连接到的虚拟节点，把该单词对应的id与这些虚拟节点对应的id相连即可。

3. 注意：beginWord加入队列开始BFS，到达endWord时的最短路径是包含了虚拟节点的，此时的最短路径是真实路径的两倍。还需要计算起点对最终答案的贡献，还需要+1

• 时间复杂度：$O(N \times C)$。其中 $N$ 为 wordList 的长度，$C$ 为列表中单词的长度。
  • 建图过程中，对于每一个单词，我们需要枚举它连接到的所有虚拟节点，时间复杂度为 $O(C)$，将这些单词加入到哈希表中，时间复杂度为 $O(N \times C)$，因此总时间复杂度为 $O(N \times C)$。
  • 广度优先搜索的时间复杂度最坏情况下是 $O(N \times C)$。每一个单词需要拓展出 $O(C)$ 个虚拟节点，因此节点数 $O(N \times C)$。
• 空间复杂度：$O(N \times C^2)$)。其中 N 为 wordList 的长度，C 为列表中单词的长度。哈希表中包含 $O(N \times C)$ 个节点，每个节点占用空间 $O(C)$，因此总的空间复杂度为 $O(N \times C^2)$。

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]):
        def addWord(word):
            # 对每个词进行标号，nodeNum为单词编号，赋值后编号+1为下一次赋值准备
            if word not in wordId:
                nonlocal nodeNum
                wordId[word] = nodeNum
                nodeNum += 1

        def addEdge(word):
            addWord(word)
            id1 = wordId[word]  # 获取当前词id
            chars = list(word)  # 将单词拆成字母
            for i in range(len(chars)):
                # 将原单词中的每一个字母拿出来，替换为*，然后对其编号，并加入边关系中
                tmp = chars[i]
                chars[i] = '*'
                newWord = ''.join(chars)
                addWord(newWord)
                id2 = wordId[newWord]
                # 将两个节点互相作为对方的一个连接对象
                edge[id1].append(id2)
                edge[id2].append(id1)
                chars[i] = tmp

        wordId = dict()     # 存放单词-id的映射
        edge = collections.defaultdict(list)    # 记录每个节点和其他（虚拟）节点的边关系
        nodeNum = 0     # 用于节点编号

        for word in wordList:
            # 对每一个词建立边关系
            addEdge(word)

        # 将beginWord加入到边关系中
        addEdge(beginWord)
        if endWord not in wordId:
            return 0
        
        dis = [float('inf')] * nodeNum  # 初始化距离
        beginId, endId = wordId[beginWord], wordId[endWord] # 起点id，重点id
        dis[beginId] = 0    # 起点id对应距离设置为0

        que = collections.deque([beginId])  # 初始化双端队列
        while que:
            x = que.popleft()
            if x == endId:
                # 如果到达终点，可以返回结果
                return dis[endId] // 2 + 1
            for it in edge[x]:
                if dis[it] == float('inf'):
                    # 上面条件表示，已经访问过，并已经修改值的，就不能再修改了
                    # 更新距离：当前距离+1
                    dis[it] = dis[x] + 1
                    que.append(it)
        return 0

核心方法：双向广度优先搜索

广度优先搜索的搜索空间大小依赖于每层节点的分支数量。加入每个节点的分支数量相等，那么搜索空间会随着层数的增长指数级的增加。

使用两个同事进行的BFS可以有效的减少搜索空间。一边从beginWord开始，一边从endWord开始。每次从两边各扩展一层节点，当发现某一时刻两边都访问过同一节点时停止。

代码住要修改的部分在于初始化距离时

		# 初始化起点距离，和对应双端队列
    	disBegin = [float("inf")] * nodeNum
        beginId = wordId[beginWord]
        disBegin[beginId] = 0
        queBegin = collections.deque([beginId])
		
        # 初始化终点距离，和对应双端队列
        disEnd = [float("inf")] * nodeNum
        endId = wordId[endWord]
        disEnd[endId] = 0
        queEnd = collections.deque([endId])

        while queBegin or queEnd:
            # 两个队列同时不为空
            queBeginSize = len(queBegin)
            for _ in range(queBeginSize):
                nodeBegin = queBegin.popleft()
                if disEnd[nodeBegin] != float("inf"):
                    # 重要！这个位置遍历过了，说明已找到这个位置，就返回结果
                    return (disBegin[nodeBegin] + disEnd[nodeBegin]) // 2 + 1
                for it in edge[nodeBegin]:
                    if disBegin[it] == float("inf"):
                        disBegin[it] = disBegin[nodeBegin] + 1
                        queBegin.append(it)

            queEndSize = len(queEnd)
            for _ in range(queEndSize):
                nodeEnd = queEnd.popleft()
                if disBegin[nodeEnd] != float("inf"):
                    return (disBegin[nodeEnd] + disEnd[nodeEnd]) // 2 + 1
                for it in edge[nodeEnd]:
                    if disEnd[it] == float("inf"):
                        disEnd[it] = disEnd[nodeEnd] + 1
                        queEnd.append(it)
        return 0

200，岛屿数量，中等

核心方法：DFS

如果一个位置为1，则以其为其实节点，开始进行DFS。在DFS过程中，每个被搜索到的1都会被重新标记为0，并且从这个位置开始，向其上下左右四个位置进行继续的DFS；如果被搜到的位置没有1，不进行任何操作。

• 时间复杂度：O(mn)，m和n分别表示行数和列数
• 空间复杂度：O(mn)，在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到 mn。

class Solution:
    def dfs(self, grid, r, c):
        # 将当前位置置为0
        grid[r][c] = '0'
        # 重新获取行列
        nr, nc = len(grid), len(grid[0])
        for x, y in [(r-1, c), (r+1, c), (r, c-1), (r, c+1)]:
            # 分别取上下左右四个位置的值，如果还等于，就继续dfs
            if 0 <= x < nr and 0 <= y < nc and grid[x][y] == '1':
                self.dfs(grid, x, y)


    def numIslands(self, grid: List[List[str]]) -> int:
        nr = len(grid)  # 获取网格的行数
        nc = len(grid[0])   # 获取网格的列数
        
        num_islands = 0 # 初始化岛屿数量
        for r in range(nr):
            for c in range(nc):
                if grid[r][c] == '1':
                    num_islands += 1
                    # 开始进行DFS
                    self.dfs(grid, r, c)
        return num_islands

核心方法：BFS

扫描整个网络，如果一个位置为1，将其加入队列，开始进行BFS，每个搜索到的 11 都会被重新标记为 00。直到队列为空，搜索结束。

• 时间复杂度：O(MN)，其中 M 和 N 分别为行数和列数。
• 空间复杂度：$O(\min(M, N))$，在最坏情况下，整个网格均为陆地，队列的大小可以达到 $\min(M, N)$。

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        nr = len(grid)  # 获取网格的行数
        nc = len(grid[0])   # 获取网格的列数
        
        num_islands = 0 # 初始化岛屿数量
        for r in range(nr):
            for c in range(nc):
                if grid[r][c] == '1':
                    num_islands += 1
                    # 和dfs的区别主要从这里开始
                    grid[r][c] = '0'
                    neighbours = collections.deque([(r, c)])    # 初始化双端队列
                    # 开始进行BFS
                    while neighbours:
                        row, col = neighbours.popleft()
                        for x, y in [(row-1, col),(row+1, col),(row, col-1),(row, col+1)]:
                            if 0 <= x < nr and 0 <= y < nc and grid[x][y] == '1':
                                neighbours.append((x,y))
                                grid[x][y] = '0'
        return num_islands

994，腐烂的橘子，中等

核心方法：BFS（本题和岛屿数量很相似）

• 首先需要确定在0时刻，总共有多少个腐烂的橘子，将腐烂橘子的坐标和时刻一同加入队列中
• 开始广度优先搜索，从队列中弹出每个已经腐烂的橘子，从这个橘子的上下左右四个方向查找是否存在好的橘子；如果存在，那么将这个位置的值重新置为2，表示已经腐烂了，时刻+1，坐标和时刻加入队列。
• 重复上述步骤，直到所有上下左右为1的位置全部遍历完毕。
• 最后检查是否还有1，如果还有表示存在不能被影响的位置，结果返回-1；否则返回时刻

时间复杂度：O(nm) 即进行一次广度优先搜索的时间，其中 m=grid[0].length，m=grid[0].length

空间复杂度：最多需要 O(nm) 的空间，即队列的大小

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        # 获取网格行列数
        R, C = len(grid), len(grid[0])

        # 记录所有腐烂橘子的位置
        queue = collections.deque()
        for r, row in enumerate(grid):
            for c, val in enumerate(row):
                if val == 2:
                    # 这里的0表示这些橘子是第0分钟开始腐烂的
                    # 将所有已经腐烂的橘子位置和时刻添加进队列中
                    queue.append((r, c, 0))
        
        # 定义四个方向的广度优先遍历
        def neighbours(r, c):
            for nr, nc in [(r-1, c), (r+1, c), (r, c-1), (r, c+1)]:
                if 0 <= nr < R and 0 <= nc < C:
                    yield nr, nc
        
        # 初始化时间，从第0分钟开始
        d = 0
        while queue:
            r, c, d = queue.popleft()
            for nr, nc in neighbours(r, c):
                if grid[nr][nc] == 1:
                    # 如果四个方向上有橘子，那么将这个位置和时刻加入队列，并重置值为2
                    grid[nr][nc] = 2
                    queue.append((nr, nc, d+1))
        
        # 检查全部腐烂后，是否还有剩余的1
        if any(1 in row for row in grid):
            return -1
        return d  

909，蛇梯棋，中等

核心方法：寻找最短路径的问题，使用广度优先遍历

注意：

• 到达的点的坐标是需要计算的。这个点的坐标与这个点的标号和棋盘的长宽有关。由于棋盘中每个位置的标号是从左下开始蛇形赋值的，那么通过计算新点编号s-1与棋盘长度的商和余数，来找到这个点的坐标；
• 因为棋盘上的位置是蛇形赋值的，所以在计算这个点的坐标时，需要注意列索引的值；在当前行下，行对2取余不等于棋盘长度对2取余时，选择当前余数；否则选择长度-1-余数
• 创建一个字典，用来记录每个位置编号下走过的距离，当走到编号为n*n的位置时，返回字典中对应的距离，就是最小距离。
• 当走到的位置是蛇或者梯子时，新节点的编号被替换为棋盘上的对应位置的数，也就是完成了通过蛇或梯子的跳跃，到达了新的位置
• 到达新的位置需要更新位置编码与对应距离，并将当前编码加入队列

时间复杂度：$O(n^2)$

空间复杂度：$O(n^2)$

class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        n = len(board)

        def get(s):
            # 获取新位置的坐标
            quot, rem = divmod(s-1, n)
            row = n - 1 - quot
            col = rem if row % 2 != n % 2 else n - 1 - rem
            return row, col

        dist = {1:0}
        queue = collections.deque([1])
        while queue:
            s1 = queue.popleft()
            if s1 == n*n:
                return dist[s1]
            for s2 in range(s1+1, min(s1+6, n*n)+1):
                r, c = get(s2)
                if board[r][c] != -1:
                    s2 = board[r][c]
                if s2 not in dist:
                    dist[s2] = dist[s1] + 1
                    queue.append(s2)
        return -1

301，删除无效括号，困难

• 所有的「括号匹配」问题，可能会用到的一个重要性质是：

  如果当前遍历到的左括号的数目严格小于右括号的数目则表达式无效。

1. 我们可以遍历一次输入字符串，统计「左括号」和「右括号」出现的次数。

• 当遍历到「右括号」的时候，
  • 如果此时「左括号」的数量不为 0，因为 「右括号」可以与之前遍历到的「左括号」匹配，此时「左括号」出现的次数 -1；如果此时「左括号」的数量为 0，「右括号」数量加 1；
• 当遍历到「左括号」的时候，「左括号」数量 +1

通过这样的计数规则，最后「左括号」和「右括号」的数量就是各自最少应该删除的数量。

2. 剪枝操作

我们设计变量 leftCount 和 rightCount 分别表示在遍历的过程中已经遍历到的左括号和右括号的数量，统计它们是为了方便剪枝。这是因为 只有当「已经遍历到的左括号的数量」严格大于「已经遍历到的右括号的数量」的时候，才可以继续添加「右括号」。

3. 对于最后找到结果去重的问题，选择哈希表。

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        # 统计原始字符串中左括号和右括号应该去掉的个数，其中右括号的匹配需要参考当前左括号的数量
        leftRemove, rightRemove = 0, 0
        for ch in s:
            if ch == '(':
                leftRemove += 1
            if ch == ')':
                if leftRemove == 0:
                    rightRemove += 1
                else:
                    leftRemove -= 1

        def dfs(idx, leftCount, rightCount, leftRemove, rightRemove, path):
            if idx == len(s):
                # 当前字符串全部遍历完，就返回递归位置
                if leftRemove == 0 and rightRemove == 0:
                    # 如果应当删除的左右括号数量全部为0，将当前情况添加进最终结果中
                    res.add(path)
                return
            # 1. 删除当前遍历字符
            if s[idx] == '(' and leftRemove:
                # 如果应删除的左括号数量不为0，递归遍历下一个字符，应删除左括号数量-1
                dfs(idx+1, leftCount, rightCount, leftRemove-1, rightRemove, path)
            if s[idx] == ')' and rightRemove:
                # 如果应删除的右阔后数量不为0，递归遍历下一个字符，应删除右括号数量-1
                dfs(idx+1, leftCount, rightCount, leftRemove, rightRemove-1, path)
            
            # 2. 保留当前遍历字符
            if s[idx] != '(' and s[idx] != ')':
                # 如果遍历到的不是括号，递归遍历下一个字符，当前字符加入当前模式
                dfs(idx+1, leftCount, rightCount, leftRemove, rightRemove, path + s[idx])
            elif s[idx] == '(':
                # 如果要保留左括号，递归遍历下一个字符，左括号数量+1，当前字符加入当前模式
                dfs(idx+1, leftCount+1, rightCount, leftRemove, rightRemove, path + s[idx])
            elif leftCount > rightCount:
                # 剪枝操作，左括号数量大于右括号数量，才能保留当前遍历到的右括号
                dfs(idx+1, leftCount, rightCount+1, leftRemove, rightRemove, path + s[idx])
            return 
        
        res = set()
        dfs(0, 0, 0, leftRemove, rightRemove, '')
        return list(res)