Update 01.Backtracking-Algorithm.md

itcharge · itcharge · commit e9c7925edb69 · 2023-02-25T23:34:58.000+08:00
diff --git a/Contents/09.Algorithm-Base/04.Backtracking-Algorithm/01.Backtracking-Algorithm.md b/Contents/09.Algorithm-Base/04.Backtracking-Algorithm/01.Backtracking-Algorithm.md
@@ -169,17 +169,34 @@ for i in range(len(nums)):          # 枚举可选元素列表
 
 **描述**：给定一个整数数组 `nums`，数组中的元素互不相同。
 
-**要求**：返回该数组所有可能的不重复子集。
+**要求**：返回该数组所有可能的不重复子集。可以按任意顺序返回解集。
+
+**说明**：
+
+- $1 \le nums.length \le 10$。
+- $-10 \le nums[i] \le 10$。
+- `nums` 中的所有元素互不相同。
 
 **示例**：
 
+- 示例 1：
+
+```Python
+输入 nums = [1,2,3]
+输出 [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
+```
+
+- 示例 2：
+
 ```Python
-输入    nums = [1,2,3]
-输出    [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
+输入：nums = [0]
+输出：[[],[0]]
 ```
 
 #### 5.1.3 解题思路
 
+##### 思路 1：回溯算法
+
 数组的每个元素都有两个选择：选与不选。
 
 我们可以通过向当前子集数组中添加可选元素来表示选择该元素。也可以在当前递归结束之后，将之前添加的元素从当前子集数组中移除（也就是回溯）来表示不选择该元素。
@@ -216,7 +233,7 @@ for i in range(len(nums)):          # 枚举可选元素列表
       - 当遍历到决策树的叶子节点时，就终止了。也就是当正在考虑的元素位置到达数组末尾（即 `start >= len(nums)`）时，递归停止。
       - 从决策树中也可以看出，子集需要存储的答案集合应该包含决策树上所有的节点，应该需要保存递归搜索的所有状态。所以无论是否达到终止条件，我们都应该将当前符合条件的结果放入到集合中。
 
-#### 5.1.4 代码
+##### 思路 1：代码
 
 ```Python
 class Solution:
@@ -237,6 +254,11 @@ class Solution:
         return res
 ```
 
+##### 思路 1：复杂度分析
+
+- **时间复杂度**：$O(n \times 2^n)$，其中 $n$ 指的是数组 `nums` 的元素个数，$2^n$ 指的是所有状态数。每种状态需要 $O(n)$ 的时间来构造子集。
+- **空间复杂度**：$O(n)$，每种状态下构造子集需要使用 $O(n)$ 的空间。
+
 ### 5.2 N 皇后
 
 #### 5.2.1 题目链接
@@ -257,16 +279,20 @@ class Solution:
 
 **示例**：
 
+- 示例 1：
+
 ```Python
-输入    n = 4
-输出    [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
-解释    如下图所示，4 皇后问题存在 2 个不同的解法。
+输入：n = 4
+输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
+解释：如下图所示，4 皇后问题存在 2 个不同的解法。
 ```
 
 ![](https://assets.leetcode.com/uploads/2020/11/13/queens.jpg)
 
 #### 5.2.3 解题思路
 
+##### 思路 1：回溯算法
+
 这道题是经典的回溯问题。我们可以按照行序来放置皇后，也就是先放第一行，再放第二行 …… 一直放到最后一行。
 
 对于 `n * n` 的棋盘来说，每一行有 `n`  列，也就有 `n` 种放法可供选择。我们可以尝试选择其中一列，查看是否与之前放置的皇后有冲突，如果没有冲突，则继续在下一行放置皇后。依次类推，直到放置完所有皇后，并且都不发生冲突时，就得到了一个合理的解。
@@ -275,7 +301,7 @@ class Solution:
 
 下面我们根据回溯算法三步走，写出对应的回溯算法。
 
-1. **明确所有选择**：根据棋盘中当前行的所有列位置上是否选择放置皇后。以 `3 * 3` 大小的棋盘为例，画出决策树，如下图所示。
+1. **明确所有选择**：根据棋盘中当前行的所有列位置上是否选择放置皇后，画出决策树，如下图所示。
 
    - ![](https://qcdn.itcharge.cn/images/20220426095225.png)
 
@@ -332,11 +358,25 @@ class Solution:
       - 当遍历到决策树的叶子节点时，就终止了。也就是在最后一行放置完皇后（即 `row == n`）时，递归停止。
       - 递归停止时，将当前符合条件的棋盘转换为答案需要的形式，然后将其存入答案数组 `res` 中即可。
 
-#### 5.2.4 代码
+##### 思路 1：代码
 
 ```Python
 class Solution:
-    # 判断当前位置 row, col 是否与之前放置的皇后发生冲突
+    res = []
+    def backtrack(self, n: int, row: int, chessboard: List[List[str]]):
+        if row == n:
+            temp_res = []
+            for temp in chessboard:
+                temp_str = ''.join(temp)
+                temp_res.append(temp_str)
+            self.res.append(temp_res)
+            return
+        for col in range(n):
+            if self.isValid(n, row, col, chessboard):
+                chessboard[row][col] = 'Q'
+                self.backtrack(n, row + 1, chessboard)
+                chessboard[row][col] = '.'
+
     def isValid(self, n: int, row: int, col: int, chessboard: List[List[str]]):
         for i in range(row):
             if chessboard[i][col] == 'Q':
@@ -348,7 +388,6 @@ class Solution:
                 return False
             i -= 1
             j -= 1
-            
         i, j = row - 1, col + 1
         while i >= 0 and j < n:
             if chessboard[i][j] == 'Q':
@@ -357,29 +396,19 @@ class Solution:
             j += 1
 
         return True
-    
+
     def solveNQueens(self, n: int) -> List[List[str]]:
-        chessboard = [['.' for _ in range(n)] for _ in range(n)]    # 棋盘初始化
+        self.res.clear()
+        chessboard = [['.' for _ in range(n)] for _ in range(n)]
+        self.backtrack(n, 0, chessboard)
+        return self.res
+```
 
-        res = []    # 存放所有符合条件结果的集合
-        def backtrack(chessboard: List[List[str]], row: int): # 正在考虑放置第 row 行的皇后
-            if row == n:                                    # 遇到终止条件
-                path = []                                   # 当前符合条件的结果
-                for ch in chessboard:
-                    row_str = ''.join(ch)
-                    path.append(row_str)
-                res.append(path)                            # 将当前符合条件的结果放入集合中
-                return
+##### 思路 1：复杂度分析
 
-            for col in range(n):                            # 枚举可放置皇后的列
-                if self.isValid(n, row, col, chessboard):   # 如果该位置与之前放置的皇后不发生冲突
-                    chessboard[row][col] = 'Q'              # 选择 row, col 位置放置皇后
-                    backtrack(chessboard, row + 1)          # 递归放置 row + 1 行之后的皇后
-                    chessboard[row][col] = '.'              # 撤销选择 row, col 位置
+- **时间复杂度**：$O(n!)$，其中 $n$ 是皇后数量。
+- **空间复杂度**：$O(n^2)$，其中 $n$ 是皇后数量。递归调用层数不会超过 $n$，每个棋盘的空间复杂度为 $O(n^2)$，所以空间复杂度为 $O(n^2)$。
 
-        backtrack(chessboard, 0)
-        return res
-```
 
 ## 参考资料
 
