目錄

一、1863. 找出所有子集的異或總和再求和 - 力扣（LeetCode）

算法代碼：

?代碼思路

問題分析

核心思想

實現細節

代碼解析

初始化

DFS 函數

時間復雜度

空間復雜度

示例運行

輸入

運行過程

總結

二、?47. 全排列 II - 力扣（LeetCode）

算法代碼：?

代碼思路

問題分析

核心思想

實現細節

代碼解析

排序

DFS 函數

剪枝條件

時間復雜度

空間復雜度

示例運行

輸入

運行過程

總結

以下是?if?條件的詳細解析：

if?條件

1.?check[i] == false

2.?i == 0

3.?nums[i] != nums[i - 1]

4.?check[i - 1] != false

if?條件的邏輯

示例說明

輸入：

排序后：

運行過程：

三、17. 電話號碼的字母組合 - 力扣（LeetCode）?

算法代碼：?

代碼思路解析

類的成員變量

主函數?letterCombinations

DFS 函數?dfs

代碼優化建議

參數傳遞優化

提前終止

代碼可讀性

優化后的代碼

總結

四、?22. 括號生成 - 力扣（LeetCode）

算法代碼：（不傳參）?

代碼思路解析

類的成員變量

主函數?generateParenthesis

DFS 函數?dfs

代碼優化建議

參數傳遞優化

提前終止

代碼可讀性

優化后的代碼

總結

算法代碼：（傳參）

五、77. 組合 - 力扣（LeetCode）

算法代碼：?

代碼思路解析

類的成員變量

主函數?combine

DFS 函數?dfs

代碼優化建議

剪枝優化

參數傳遞優化

代碼可讀性

優化后的代碼

優化點詳解

剪枝優化

回溯的恢復現場

總結

六、494. 目標和 - 力扣（LeetCode）?

算法代碼：?

代碼思路解析

類的成員變量

主函數?findTargetSumWays

DFS 函數?dfs

把?path?改為全局變量時會超時，為什么呢？

回溯的恢復現場問題

遞歸調用棧的深度

多線程問題

代碼可讀性和調試難度

問題分析：

總結

七、39. 組合總和 - 力扣（LeetCode）

解法一：算法代碼（回溯）

代碼思路解析

類的成員變量

主函數?combinationSum

DFS 函數?dfs

解法二：算法代碼（無限次使用判斷有無越界）

代碼思路解析

類的成員變量

主函數?combinationSum

DFS 函數?dfs

代碼優化建議

剪枝優化

恢復現場的優化

代碼可讀性

優化后的代碼

代碼細節解析

枚舉?k?的作用

恢復現場

遞歸調用

總結

八、?784. 字母大小寫全排列 - 力扣（LeetCode）

算法代碼：?

代碼思路解析

類的成員變量

主函數?letterCasePermutation

DFS 函數?dfs

輔助函數?change

代碼優化建議

減少函數調用

剪枝優化

代碼可讀性

優化后的代碼

代碼細節解析

不改變字符

改變字符大小寫

剪枝優化

總結

九、526. 優美的排列 - 力扣（LeetCode）?

算法代碼：?

代碼思路解析

類的成員變量

主函數?countArrangement

DFS 函數?dfs

代碼優化建議

剪枝優化

代碼可讀性

優化后的代碼

代碼細節解析

check?數組的作用

剪枝條件

回溯的恢復現場

總結

十、?51. N 皇后 - 力扣（LeetCode）

算法代碼：?

代碼思路解析

類的成員變量

主函數?solveNQueens

DFS 函數?dfs

代碼優化建議

剪枝優化

代碼可讀性

優化后的代碼

代碼細節解析

checkCol、checkDig1、checkDig2?的作用

放置皇后

回溯的恢復現場

總結

十一、36. 有效的數獨 - 力扣（LeetCode）?

?算法代碼：

代碼思路解析

數據結構

遍歷棋盤

檢查有效性

返回結果

代碼優化建議

總結：

十二、?37. 解數獨 - 力扣（LeetCode）

算法代碼：?

代碼思路解析

數據結構

初始化

深度優先搜索（DFS）

回溯

終止條件

代碼優化建議

總結

十三、?79. 單詞搜索 - 力扣（LeetCode）

?算法代碼：

代碼思路解析

數據結構

主函數?exist

深度優先搜索（DFS）函數?dfs

回溯

代碼優化建議

總結

十四、?1219. 黃金礦工 - 力扣（LeetCode）

算法代碼：?

代碼思路解析

數據結構

主函數?getMaximumGold

深度優先搜索（DFS）函數?dfs

回溯

代碼優化建議

總結

十五、980. 不同路徑 III - 力扣（LeetCode）?

算法代碼：

代碼思路解析

數據結構

主函數?uniquePathsIII

深度優先搜索（DFS）函數?dfs

回溯

代碼優化建議

總結

---

一、1863. 找出所有子集的異或總和再求和 - 力扣（LeetCode）

算法代碼：

class Solution {int path;  // 當前子集的異或和int sum;   // 所有子集異或和的總和public:int subsetXORSum(vector<int>& nums) {path = 0;  // 初始化 pathsum = 0;   // 初始化 sumdfs(nums, 0);  // 從第 0 個元素開始 DFSreturn sum;}void dfs(vector<int>& nums, int pos) {sum += path;  // 將當前子集的異或和累加到 sumfor (int i = pos; i < nums.size(); i++) {path ^= nums[i];  // 將 nums[i] 加入當前子集，更新 pathdfs(nums, i + 1);  // 遞歸處理下一個元素path ^= nums[i];   // 回溯，恢復 path 的值}}
};

?代碼思路

1. 問題分析

   • 給定一個數組?nums，需要計算所有子集的異或和的總和。

   • 例如，nums = [1, 2, 3]，子集包括?[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]，它們的異或和分別為?0, 1, 2, 3, 3, 2, 1, 0，總和為?0 + 1 + 2 + 3 + 3 + 2 + 1 + 0 = 12。

2. 核心思想

   • 使用深度優先搜索（DFS）遍歷所有可能的子集。

   • 在 DFS 過程中，維護一個變量?path，表示當前子集的異或和。

   • 每次遞歸時，將當前子集的異或和?path?累加到?sum?中。

   • 通過回溯恢復現場，確保?path?的正確性。

3. 實現細節

   • path：表示當前子集的異或和。

   • sum：表示所有子集異或和的總和。

   • dfs?函數：

     • 將當前?path?的值累加到?sum。

     • 遍歷數組?nums，從當前位置?pos?開始，逐個嘗試將元素加入當前子集。

     • 遞歸調用?dfs，繼續處理下一個元素。

     • 回溯時，恢復?path?的值（通過再次異或當前元素）。

---

代碼解析

1. 初始化

   • path?和?sum?初始化為 0。

2. DFS 函數

   • 累加當前子集的異或和：sum += path。

   • 遍歷數組：

     • 將當前元素?nums[i]?異或到?path?中，表示將其加入當前子集。

     • 遞歸調用?dfs，處理下一個元素。

     • 回溯時，再次異或?nums[i]，恢復?path?的值。

3. 時間復雜度

   • 由于每個元素有兩種選擇（加入或不加入子集），總共有?2n?個子集，因此時間復雜度為?O(2n)。

4. 空間復雜度

   • 遞歸棧的深度為?O(n)，因此空間復雜度為?O(n)。

---

示例運行

輸入

nums = [1, 2, 3];

運行過程

1. 初始狀態：path = 0,?sum = 0。

2. DFS 遍歷所有子集：

   • []：path = 0，sum += 0。

   • [1]：path = 1，sum += 1。

   • [1, 2]：path = 3，sum += 3。

   • [1, 2, 3]：path = 0，sum += 0。

   • [1, 3]：path = 2，sum += 2。

   • [2]：path = 2，sum += 2。

   • [2, 3]：path = 1，sum += 1。

   • [3]：path = 3，sum += 3。

3. 最終結果：sum = 0 + 1 + 3 + 0 + 2 + 2 + 1 + 3 = 12。

---

總結

• 這段代碼通過 DFS 和回溯，高效地計算了所有子集的異或和的總和。

• 核心思想是利用遞歸遍歷所有可能的子集，并通過回溯恢復現場，確保計算的正確性。

• 代碼簡潔清晰，適合解決類似子集相關的問題。

二、?47. 全排列 II - 力扣（LeetCode）

算法代碼：?

class Solution {vector<int> path;           // 當前生成的排列vector<vector<int>> ret;    // 所有不重復的排列bool check[9];              // 記錄元素是否被使用過public:vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(), nums.end());  // 排序，方便剪枝dfs(nums, 0);                   // 從第 0 個位置開始 DFSreturn ret;}void dfs(vector<int>& nums, int pos) {if (pos == nums.size()) {ret.push_back(path);  // 當前排列完成，加入結果集return;}for (int i = 0; i < nums.size(); i++) {// 剪枝條件if (check[i] == false &&(i == 0 || nums[i] != nums[i - 1] || check[i - 1] != false)) {path.push_back(nums[i]);  // 將 nums[i] 加入當前排列check[i] = true;         // 標記 nums[i] 已被使用dfs(nums, pos + 1);      // 遞歸處理下一個位置path.pop_back();          // 回溯，恢復 pathcheck[i] = false;        // 回溯，恢復 check}}}
};

代碼思路

1. 問題分析

   • 給定一個可能包含重復元素的數組?nums，需要生成所有不重復的全排列。

   • 例如，nums = [1, 1, 2]，不重復的全排列為?[[1,1,2], [1,2,1], [2,1,1]]。

2. 核心思想

   • 使用深度優先搜索（DFS）生成所有可能的排列。

   • 通過排序和剪枝，避免生成重復的排列。

   • 使用一個布爾數組?check?記錄哪些元素已經被使用過。

3. 實現細節

   • path：記錄當前生成的排列。

   • ret：存儲所有不重復的排列。

   • check：記錄每個元素是否已經被使用。

   • dfs?函數：

     • 如果當前排列的長度等于?nums?的長度，將其加入?ret。

     • 遍歷數組?nums，嘗試將未使用的元素加入當前排列。

     • 通過剪枝條件避免重復排列。

     • 回溯時恢復現場，確保?path?和?check?的正確性。

---

代碼解析

1. 排序

   • 對數組?nums?進行排序，使得相同的元素相鄰，方便剪枝。

2. DFS 函數

   • 終止條件：如果當前排列的長度等于?nums?的長度，將其加入?ret。

   • 遍歷數組：

     • 如果當前元素未被使用（check[i] == false），并且滿足剪枝條件，則將其加入當前排列。

     • 遞歸調用?dfs，處理下一個位置。

     • 回溯時，恢復?path?和?check?的值。

3. 剪枝條件

   • i == 0：第一個元素無需判斷是否重復。

   • nums[i] != nums[i - 1]：當前元素與前一個元素不同，無需剪枝。

   • check[i - 1] != false：前一個相同元素已被使用，說明當前元素是新的排列起點。

4. 時間復雜度

   • 最壞情況下，所有排列都不重復，時間復雜度為?O(n×n!)O(n×n!)，其中?n!n!?是排列數，nn?是生成每個排列的時間。

5. 空間復雜度

   • 遞歸棧的深度為?O(n)O(n)，結果集?ret?的空間為?O(n×n!)O(n×n!)。

---

示例運行

輸入

nums = [1, 1, 2];

運行過程

1. 排序后：nums = [1, 1, 2]。

2. DFS 遍歷：

   • 生成?[1, 1, 2]。

   • 生成?[1, 2, 1]。

   • 生成?[2, 1, 1]。

3. 最終結果：ret = [[1,1,2], [1,2,1], [2,1,1]]。

---

總結

• 這段代碼通過 DFS 和剪枝，高效地生成了所有不重復的全排列。

• 核心思想是利用排序和剪枝條件，避免重復排列的生成。

• 代碼簡潔清晰，適合解決類似排列相關的問題。

在代碼中，if?條件的寫法是為了避免生成重復的排列，尤其是在數組?nums?包含重復元素的情況下。這個條件的作用是剪枝，即跳過不必要的遞歸分支，從而減少重復計算。

以下是?if?條件的詳細解析：

---

if?條件

if (check[i] == false &&(i == 0 || nums[i] != nums[i - 1] || check[i - 1] != false))

1.?check[i] == false

• 作用：確保當前元素?nums[i]?未被使用過。

• 解釋：

  • check[i]?是一個布爾數組，記錄?nums[i]?是否已經被加入當前排列。

  • 如果?check[i] == true，說明?nums[i]?已經被使用過，不能重復使用。

2.?i == 0

• 作用：處理第一個元素，避免越界。

• 解釋：

  • 當?i == 0?時，nums[i - 1]?不存在，因此不需要判斷?nums[i] != nums[i - 1]?或?check[i - 1] != false。

3.?nums[i] != nums[i - 1]

• 作用：確保當前元素與前一個元素不同。

• 解釋：

  • 如果?nums[i] == nums[i - 1]，說明當前元素和前一個元素相同。

  • 為了避免重復排列，只有當當前元素與前一個元素不同時，才繼續遞歸。

4.?check[i - 1] != false

• 作用：確保前一個相同元素已經被使用過。

• 解釋：

  • 如果?nums[i] == nums[i - 1]，并且?check[i - 1] == false，說明前一個相同元素未被使用過。

  • 這種情況下，如果直接使用?nums[i]，會導致重復排列。

  • 只有當?check[i - 1] != false（即前一個相同元素已經被使用過），才允許使用?nums[i]。

---

if?條件的邏輯

• 整體邏輯：

  • 如果當前元素未被使用過（check[i] == false），并且滿足以下條件之一：

    1. 當前元素是第一個元素（i == 0）。

    2. 當前元素與前一個元素不同（nums[i] != nums[i - 1]）。

    3. 前一個相同元素已經被使用過（check[i - 1] != false）。

  • 則繼續遞歸，否則跳過。

• 為什么這樣寫：

  • 通過排序，相同的元素會相鄰。

  • 對于相同的元素，只有當前一個相同元素已經被使用過時，才允許使用當前元素。

  • 這樣可以避免生成重復的排列。

---

示例說明

輸入：

nums = [1, 1, 2];

排序后：

nums = [1, 1, 2];

運行過程：

1. 第一次遞歸：

   • 選擇?nums[0] = 1，check[0] = true。

   • 進入下一層遞歸。

2. 第二次遞歸：

   • 選擇?nums[1] = 1，此時?nums[1] == nums[0]，但?check[0] == true，因此允許選擇。

   • check[1] = true。

   • 進入下一層遞歸。

3. 第三次遞歸：

   • 選擇?nums[2] = 2，check[2] = true。

   • 生成排列?[1, 1, 2]。

4. 回溯：

   • 恢復?check[2] = false。

   • 恢復?check[1] = false。

   • 恢復?check[0] = false。

5. 第二次遞歸（另一種選擇）：

   • 選擇?nums[2] = 2，check[2] = true。

   • 進入下一層遞歸。

6. 第三次遞歸：

   • 選擇?nums[0] = 1，check[0] = true。

   • 生成排列?[1, 2, 1]。

7. 回溯：

   • 恢復?check[0] = false。

   • 恢復?check[2] = false。

8. 繼續遞歸：

   • 類似過程生成?[2, 1, 1]。

三、17. 電話號碼的字母組合 - 力扣（LeetCode）?

算法代碼：?

class Solution {string hash[10] = {"",    "",    "abc",  "def", "ghi","jkl", "mno", "pqrs", "tuv", "wxyz"};string path;vector<string> ret;public:vector<string> letterCombinations(string digits) {if (digits.size() == 0)return ret;dfs(digits, 0);return ret;}void dfs(string& digits, int pos) {if (pos == digits.size()) {ret.push_back(path);return;}for (auto ch : hash[digits[pos] - '0']) {path.push_back(ch);dfs(digits, pos + 1);path.pop_back(); // 恢復現場}}
};

????????這段代碼的目的是生成給定數字字符串?digits?所代表的所有可能的字母組合。例如，輸入?"23"，輸出?["ad","ae","af","bd","be","bf","cd","ce","cf"]。代碼使用了深度優先搜索（DFS）來遍歷所有可能的組合。

代碼思路解析

1. 類的成員變量

   • hash[10]：一個字符串數組，存儲了每個數字對應的字母。例如，2?對應?"abc"，3?對應?"def"，依此類推。

   • path：一個字符串，用于存儲當前正在構建的字母組合。

   • ret：一個字符串向量，用于存儲所有可能的字母組合。

2. 主函數?letterCombinations

   • 首先檢查輸入字符串?digits?是否為空。如果為空，直接返回空的?ret。

   • 否則，調用?dfs?函數開始深度優先搜索。

3. DFS 函數?dfs

   • pos?參數表示當前處理到?digits?中的第幾個字符。

   • 如果?pos?等于?digits?的長度，說明已經處理完所有字符，當前的?path?就是一個完整的字母組合，將其加入?ret?中。

   • 否則，遍歷當前數字對應的所有字母（通過?hash[digits[pos] - '0']?獲取），并將每個字母依次加入?path?中，然后遞歸調用?dfs?處理下一個字符。

   • 遞歸調用結束后，通過?path.pop_back()?恢復現場，以便嘗試下一個字母。

代碼優化建議

1. 參數傳遞優化

   • digits?和?path?可以通過引用傳遞，避免不必要的拷貝。

2. 提前終止

   • 如果?digits?為空，可以直接返回空結果，不需要進入 DFS。

3. 代碼可讀性

   • 可以添加注釋，解釋每個步驟的作用，方便他人理解。

優化后的代碼

class Solution {// 數字到字母的映射const string hash[10] = {"",    "",    "abc",  "def", "ghi","jkl", "mno", "pqrs", "tuv", "wxyz"};string path; // 當前路徑vector<string> ret; // 結果集public:vector<string> letterCombinations(string digits) {if (digits.empty()) {return ret; // 如果輸入為空，直接返回空結果}dfs(digits, 0); // 開始深度優先搜索return ret;}void dfs(const string& digits, int pos) {if (pos == digits.size()) {ret.push_back(path); // 找到一個完整的組合，加入結果集return;}// 遍歷當前數字對應的所有字母for (char ch : hash[digits[pos] - '0']) {path.push_back(ch); // 選擇當前字母dfs(digits, pos + 1); // 遞歸處理下一個數字path.pop_back(); // 回溯，撤銷選擇}}
};

總結

????????這段代碼的核心思想是通過 DFS 遍歷所有可能的字母組合，并通過回溯來恢復現場，確保每個組合都被正確生成。代碼結構清晰，邏輯簡單，適合處理這類組合問題。

四、?22. 括號生成 - 力扣（LeetCode）

算法代碼：（不傳參）?

class Solution {int left, right, n;string path;vector<string> ret;public:vector<string> generateParenthesis(int _n) {n = _n;dfs();return ret;}void dfs() {if (right == n) {ret.push_back(path);return;}if (left < n) // 添加左括號{path.push_back('(');left++;dfs();path.pop_back();left--; // 恢復現場}if (right < left) // 添加右括號{path.push_back(')');right++;dfs();path.pop_back();right--; // 恢復現場}}
};

????????這段代碼的目的是生成所有有效的括號組合，給定一個整數?n，表示生成?n?對括號。例如，當?n = 3?時，輸出?["((()))","(()())","(())()","()(())","()()()"]。代碼使用了深度優先搜索（DFS）和回溯的思想來遍歷所有可能的組合。

代碼思路解析

1. 類的成員變量

   • left：記錄當前路徑中左括號的數量。

   • right：記錄當前路徑中右括號的數量。

   • n：表示需要生成的括號對數。

   • path：一個字符串，用于存儲當前正在構建的括號組合。

   • ret：一個字符串向量，用于存儲所有有效的括號組合。

2. 主函數?generateParenthesis

   • 初始化?n?為輸入的?_n。

   • 調用?dfs?函數開始深度優先搜索。

   • 返回結果?ret。

3. DFS 函數?dfs

   • 如果?right == n，說明當前路徑中的右括號數量已經達到?n，即已經生成了一個有效的括號組合，將其加入?ret?中。

   • 如果?left < n，說明還可以添加左括號：

     • 將左括號?(?加入?path?中。

     • 增加?left?的計數。

     • 遞歸調用?dfs。

     • 回溯時，移除剛剛添加的左括號，并減少?left?的計數。

   • 如果?right < left，說明可以添加右括號：

     • 將右括號?)?加入?path?中。

     • 增加?right?的計數。

     • 遞歸調用?dfs。

     • 回溯時，移除剛剛添加的右括號，并減少?right?的計數。

代碼優化建議

1. 參數傳遞優化

   • path?可以通過引用傳遞，避免不必要的拷貝。

2. 提前終止

   • 如果?left?或?right?超過?n，可以直接返回，避免無效的遞歸調用。

3. 代碼可讀性

   • 可以添加注釋，解釋每個步驟的作用，方便他人理解。

優化后的代碼

class Solution {int left, right, n; // left: 當前左括號數量，right: 當前右括號數量，n: 總括號對數string path; // 當前路徑vector<string> ret; // 結果集public:vector<string> generateParenthesis(int _n) {n = _n;dfs(); // 開始深度優先搜索return ret;}void dfs() {if (right == n) {ret.push_back(path); // 找到一個有效的括號組合，加入結果集return;}if (left < n) { // 可以添加左括號path.push_back('('); // 選擇左括號left++; // 增加左括號計數dfs(); // 遞歸處理path.pop_back(); // 回溯，撤銷選擇left--; // 恢復左括號計數}if (right < left) { // 可以添加右括號path.push_back(')'); // 選擇右括號right++; // 增加右括號計數dfs(); // 遞歸處理path.pop_back(); // 回溯，撤銷選擇right--; // 恢復右括號計數}}
};

總結

????????這段代碼的核心思想是通過 DFS 遍歷所有可能的括號組合，并通過回溯來恢復現場，確保每個組合都是有效的。代碼結構清晰，邏輯簡單，適合處理這類組合問題。通過限制左括號和右括號的數量，確保生成的括號組合始終是有效的。

算法代碼：（傳參）

class Solution {vector<string> ret; // 結果集public:vector<string> generateParenthesis(int n) {dfs(0, 0, n, ""); // 開始深度優先搜索return ret;}void dfs(int left, int right, int n, string path) {if (right == n) {ret.push_back(path); // 找到一個有效的括號組合，加入結果集return;}if (left < n) { // 可以添加左括號dfs(left + 1, right, n, path + '('); // 選擇左括號，遞歸處理}if (right < left) { // 可以添加右括號dfs(left, right + 1, n, path + ')'); // 選擇右括號，遞歸處理}}
};

五、77. 組合 - 力扣（LeetCode）

算法代碼：?

class Solution {vector<int> path;vector<vector<int>> ret;int n, k;public:vector<vector<int>> combine(int _n, int _k) {n = _n;k = _k;dfs(1);return ret;}void dfs(int start) {if (path.size() == k) {ret.push_back(path);return;}for (int i = start; i <= n; i++) {path.push_back(i);dfs(i + 1);path.pop_back(); // 恢復現場}}
};

????????這段代碼的目的是生成從?1?到?n?中所有可能的?k?個數的組合。例如，當?n = 4，k = 2?時，輸出?[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]。代碼使用了深度優先搜索（DFS）和回溯的思想來遍歷所有可能的組合。

---

代碼思路解析

1. 類的成員變量

   • path：一個整數向量，用于存儲當前正在構建的組合。

   • ret：一個二維整數向量，用于存儲所有可能的組合。

   • n：表示數字范圍的上限（從?1?到?n）。

   • k：表示每個組合中數字的個數。

2. 主函數?combine

   • 初始化?n?和?k?為輸入的?_n?和?_k。

   • 調用?dfs(1)?開始深度優先搜索，從數字?1?開始。

   • 返回結果?ret。

3. DFS 函數?dfs

   • start?參數表示當前可以選擇的起始數字。

   • 如果?path.size() == k，說明當前路徑中的數字數量已經達到?k，即已經生成了一個有效的組合，將其加入?ret?中。

   • 否則，從?start?開始遍歷到?n：

     • 將當前數字?i?加入?path?中。

     • 遞歸調用?dfs(i + 1)，確保下一個數字比當前數字大，避免重復組合。

     • 回溯時，移除剛剛添加的數字?i，恢復現場。

---

代碼優化建議

1. 剪枝優化

   • 在遍歷時，如果剩余的數字不足以填滿?k?個數的組合，可以直接跳過。例如，當?path.size() + (n - i + 1) < k?時，可以直接?break。

2. 參數傳遞優化

   • path?可以通過引用傳遞，避免不必要的拷貝。

3. 代碼可讀性

   • 可以添加注釋，解釋每個步驟的作用，方便他人理解。

---

優化后的代碼

class Solution {vector<int> path; // 當前路徑vector<vector<int>> ret; // 結果集int n, k; // n: 數字范圍上限，k: 組合中數字的個數public:vector<vector<int>> combine(int _n, int _k) {n = _n;k = _k;dfs(1); // 從數字 1 開始深度優先搜索return ret;}void dfs(int start) {if (path.size() == k) {ret.push_back(path); // 找到一個有效的組合，加入結果集return;}// 剪枝：如果剩余的數字不足以填滿 k 個數的組合，直接返回for (int i = start; i <= n - (k - path.size()) + 1; i++) {path.push_back(i); // 選擇當前數字dfs(i + 1); // 遞歸處理下一個數字path.pop_back(); // 回溯，撤銷選擇}}
};

---

優化點詳解

1. 剪枝優化

   • 在?for?循環中，i?的上限從?n?改為?n - (k - path.size()) + 1。

   • 這是因為如果剩余的數字不足以填滿?k?個數的組合，繼續遍歷是沒有意義的。

   • 例如，當?n = 4，k = 2，且?path.size() = 1?時，i?的最大值應該是?3（因為?4?只能和?5?組合，但?5?超出了范圍）。

2. 回溯的恢復現場

   • 在遞歸調用結束后，通過?path.pop_back()?移除剛剛添加的數字，確保?path?恢復到之前的狀態。

---

總結

????????這段代碼的核心思想是通過 DFS 遍歷所有可能的組合，并通過回溯來恢復現場，確保每個組合都是唯一的。通過剪枝優化，可以減少不必要的遞歸調用，提高代碼效率。代碼結構清晰，邏輯簡單，適合處理這類組合問題。

六、494. 目標和 - 力扣（LeetCode）?

算法代碼：?

class Solution {int ret, aim; // ret: 滿足條件的組合數量，aim: 目標值public:int findTargetSumWays(vector<int>& nums, int target) {aim = target;dfs(nums, 0, 0); // 從數組的第一個位置和初始路徑和開始return ret;}void dfs(vector<int>& nums, int pos, int path) {if (pos == nums.size()) { // 已經處理完所有數字if (path == aim) { // 如果當前路徑和等于目標值ret++; // 增加滿足條件的組合數量}return;}// 加法dfs(nums, pos + 1, path + nums[pos]);// 減法dfs(nums, pos + 1, path - nums[pos]);}
};

????????這段代碼的目的是在給定一個整數數組?nums?和一個目標值?target?的情況下，計算有多少種不同的方式可以通過在數組中的每個數字前添加?+?或?-，使得表達式的值等于?target。例如，nums = [1,1,1,1,1]，target = 3，輸出?5。

代碼使用了深度優先搜索（DFS）來遍歷所有可能的加減組合，并通過回溯的方式統計滿足條件的組合數量。

---

代碼思路解析

1. 類的成員變量

   • ret：用于記錄滿足條件的組合數量。

   • aim：存儲目標值?target。

2. 主函數?findTargetSumWays

   • 初始化?aim?為?target。

   • 調用?dfs(nums, 0, 0)?開始深度優先搜索，從數組的第一個位置（pos = 0）和初始路徑和（path = 0）開始。

   • 返回結果?ret。

3. DFS 函數?dfs

   • nums：輸入的整數數組。

   • pos：當前處理到的數組位置。

   • path：當前路徑的和（即當前表達式的值）。

   • 如果?pos == nums.size()，說明已經處理完所有數字，檢查當前路徑和是否等于?aim。如果相等，ret++。

   • 否則，分別嘗試對當前數字進行加法和減法操作，并遞歸調用?dfs。

---

class Solution {int ret, aim, path; // path 改為全局變量public:int findTargetSumWays(vector<int>& nums, int target) {aim = target;path = 0; // 初始化 pathdfs(nums, 0);return ret;}void dfs(vector<int>& nums, int pos) {if (pos == nums.size()) {if (path == aim) {ret++;}return;}// 加法path += nums[pos]; // 修改全局變量 pathdfs(nums, pos + 1);path -= nums[pos]; // 恢復現場// 減法path -= nums[pos]; // 修改全局變量 pathdfs(nums, pos + 1);path += nums[pos]; // 恢復現場}
};

把?path?改為全局變量時會超時，為什么呢？

如果將?path?改為全局變量（即類的成員變量），代碼可能會超時，原因如下：

1. 回溯的恢復現場問題

   • 在當前的實現中，path?是通過參數傳遞的，每次遞歸調用都會創建一個新的?path?值。這樣，在回溯時不需要手動恢復?path?的狀態。

   • 如果將?path?改為全局變量，每次遞歸調用都會修改同一個?path?變量。在回溯時，必須手動恢復?path?的狀態（例如，path -= nums[pos]?或?path += nums[pos]），否則會導致狀態混亂。

2. 遞歸調用棧的深度

   • 如果?path?是全局變量，每次遞歸調用都會修改同一個變量，這會導致遞歸調用棧的深度增加，從而增加時間和空間復雜度。

   • 而通過參數傳遞?path，每次遞歸調用都會創建一個新的?path?值，遞歸調用棧的深度不會增加。

3. 多線程問題

   • 如果代碼在多線程環境中運行，全局變量?path?可能會導致線程安全問題。而通過參數傳遞?path，每個線程可以維護自己的狀態。

4. 代碼可讀性和調試難度

   • 使用全局變量?path?會使代碼的邏輯變得復雜，尤其是在回溯時需要手動恢復狀態。這會增加調試的難度。

   • 通過參數傳遞?path，代碼的邏輯更加清晰，調試也更加方便。

---

問題分析：

• 每次遞歸調用都會修改全局變量?path，導致回溯時需要手動恢復狀態。

• 如果忘記恢復狀態，會導致錯誤的結果。

• 遞歸調用棧的深度增加，可能導致超時。

---

總結

• path?作為參數：每次遞歸調用都會創建一個新的?path?值，回溯時不需要手動恢復狀態，代碼邏輯清晰，效率高。

• path?作為全局變量：需要手動恢復狀態，容易出錯，遞歸調用棧深度增加，可能導致超時。

因此，在這種回溯問題中，推薦將?path?作為參數傳遞，而不是作為全局變量。

七、39. 組合總和 - 力扣（LeetCode）

解法一：算法代碼（回溯）

class Solution {vector<vector<int>> ret; // 存儲所有滿足條件的組合vector<int> path; // 當前路徑public:vector<vector<int>> combinationSum(vector<int>& nums, int target) {dfs(nums, target, 0); // 開始深度優先搜索return ret;}void dfs(vector<int>& nums, int target, int start) {if (target == 0) { // 如果目標值為0，說明當前路徑滿足條件ret.push_back(path);return;}if (target < 0) { // 如果目標值小于0，說明當前路徑不滿足條件return;}for (int i = start; i < nums.size(); i++) { // 從start開始遍歷數組path.push_back(nums[i]); // 選擇當前數字dfs(nums, target - nums[i], i); // 遞歸處理，注意可以重復選擇當前數字path.pop_back(); // 回溯，撤銷選擇}}
};

代碼思路解析

1. 類的成員變量

   • ret：用于存儲所有滿足條件的組合。

   • path：用于存儲當前正在構建的組合。

2. 主函數?combinationSum

   • 調用?dfs(nums, target, 0)?開始深度優先搜索，從數組的第一個位置開始。

3. DFS 函數?dfs

   • nums：輸入的整數數組。

   • target：當前剩余的目標值。

   • start：當前處理到的數組位置。

   • 如果?target == 0，說明當前路徑的和等于目標值，將?path?加入?ret?中。

   • 如果?target < 0，說明當前路徑的和已經超過目標值，直接返回。

   • 否則，從?start?開始遍歷數組：

     • 將當前數字?nums[i]?加入?path?中。

     • 遞歸調用?dfs(nums, target - nums[i], i)，允許重復選擇當前數字。

     • 回溯時，移除剛剛添加的數字?nums[i]，恢復現場。

解法二：算法代碼（無限次使用判斷有無越界）

class Solution {int aim;vector<int> path;vector<vector<int>> ret;public:vector<vector<int>> combinationSum(vector<int>& nums, int target) {aim = target;dfs(nums, 0, 0);return ret;}void dfs(vector<int>& nums, int pos, int sum) {if (sum == aim) {ret.push_back(path);return;}if (sum > aim || pos == nums.size())return;// 枚舉個數for (int k = 0; k * nums[pos] + sum <= aim; k++) {if (k)path.push_back(nums[pos]);dfs(nums, pos + 1, sum + k * nums[pos]);}// 恢復現場for (int k = 1; k * nums[pos] + sum <= aim; k++) {path.pop_back();}}
};

????????這段代碼的目的是在給定一個無重復元素的整數數組?nums?和一個目標值?target?的情況下，找出所有滿足和為?target?的組合。數組中的數字可以無限次使用（即允許重復選擇）。例如，nums = [2,3,6,7]，target = 7，輸出?[[2,2,3],[7]]。

????????代碼使用了深度優先搜索（DFS）和回溯的思想來遍歷所有可能的組合，并通過剪枝優化減少不必要的遞歸調用。

---

代碼思路解析

1. 類的成員變量

   • aim：存儲目標值?target。

   • path：一個整數向量，用于存儲當前正在構建的組合。

   • ret：一個二維整數向量，用于存儲所有滿足條件的組合。

2. 主函數?combinationSum

   • 初始化?aim?為?target。

   • 調用?dfs(nums, 0, 0)?開始深度優先搜索，從數組的第一個位置（pos = 0）和初始和（sum = 0）開始。

   • 返回結果?ret。

3. DFS 函數?dfs

   • nums：輸入的整數數組。

   • pos：當前處理到的數組位置。

   • sum：當前路徑的和。

   • 如果?sum == aim，說明當前路徑的和等于目標值，將?path?加入?ret?中。

   • 如果?sum > aim?或?pos == nums.size()，說明當前路徑的和已經超過目標值，或者已經處理完所有數字，直接返回。

   • 否則，枚舉當前數字?nums[pos]?的使用次數?k：

     • 如果?k > 0，將?nums[pos]?加入?path?中。

     • 遞歸調用?dfs(nums, pos + 1, sum + k * nums[pos])，處理下一個數字。

   • 回溯時，恢復現場，將?nums[pos]?從?path?中移除。

---

代碼優化建議

1. 剪枝優化

   • 在枚舉?k?時，可以通過?k * nums[pos] + sum <= aim?來限制?k?的最大值，避免不必要的遞歸調用。

2. 恢復現場的優化

   • 在回溯時，可以通過一個循環將?nums[pos]?從?path?中移除，確保?path?恢復到之前的狀態。

3. 代碼可讀性

   • 可以添加注釋，解釋每個步驟的作用，方便他人理解。

---

優化后的代碼

class Solution {int aim; // 目標值vector<int> path; // 當前路徑vector<vector<int>> ret; // 結果集public:vector<vector<int>> combinationSum(vector<int>& nums, int target) {aim = target;dfs(nums, 0, 0); // 從數組的第一個位置和初始和開始return ret;}void dfs(vector<int>& nums, int pos, int sum) {if (sum == aim) { // 當前路徑和等于目標值ret.push_back(path); // 將當前路徑加入結果集return;}if (sum > aim || pos == nums.size()) { // 剪枝：當前路徑和超過目標值，或者已經處理完所有數字return;}// 枚舉當前數字的使用次數for (int k = 0; k * nums[pos] + sum <= aim; k++) {if (k > 0) { // 如果 k > 0，將當前數字加入路徑path.push_back(nums[pos]);}dfs(nums, pos + 1, sum + k * nums[pos]); // 遞歸處理下一個數字}// 恢復現場：將當前數字從路徑中移除for (int k = 1; k * nums[pos] + sum <= aim; k++) {path.pop_back();}}
};

---

代碼細節解析

1. 枚舉?k?的作用

   • k?表示當前數字?nums[pos]?的使用次數。

   • 通過?k * nums[pos] + sum <= aim?限制?k?的最大值，避免不必要的遞歸調用。

2. 恢復現場

   • 在回溯時，通過一個循環將?nums[pos]?從?path?中移除，確保?path?恢復到之前的狀態。

3. 遞歸調用

   • 每次遞歸調用都會處理下一個數字（pos + 1），并更新當前路徑和（sum + k * nums[pos]）。

---

總結

????????這段代碼的核心思想是通過 DFS 遍歷所有可能的組合，并通過回溯來恢復現場，確保每個組合都是有效的。通過枚舉?k?來限制當前數字的使用次數，并通過剪枝優化減少不必要的遞歸調用。代碼結構清晰，邏輯簡單，適合處理這類組合問題。

八、?784. 字母大小寫全排列 - 力扣（LeetCode）

算法代碼：?

class Solution {string path;vector<string> ret;public:vector<string> letterCasePermutation(string s) {dfs(s, 0);return ret;}void dfs(string& s, int pos) {if (pos == s.length()) {ret.push_back(path);return;}char ch = s[pos];// 不改變path.push_back(ch);dfs(s, pos + 1);path.pop_back(); // 恢復現場// 改變if (ch < '0' || ch > '9') {char tmp = change(ch);path.push_back(tmp);dfs(s, pos + 1);path.pop_back(); // 恢復現場}}char change(char ch) {if (ch >= 'a' && ch <= 'z')ch -= 32;elsech += 32;return ch;}
};

????????這段代碼的目的是生成給定字符串?s?的所有可能的字母大小寫排列組合。例如，輸入?s = "a1b2"，輸出?["a1b2","a1B2","A1b2","A1B2"]。代碼使用了深度優先搜索（DFS）和回溯的思想來遍歷所有可能的組合。

---

代碼思路解析

1. 類的成員變量

   • path：一個字符串，用于存儲當前正在構建的排列組合。

   • ret：一個字符串向量，用于存儲所有可能的排列組合。

2. 主函數?letterCasePermutation

   • 調用?dfs(s, 0)?開始深度優先搜索，從字符串的第一個字符（pos = 0）開始。

   • 返回結果?ret。

3. DFS 函數?dfs

   • s：輸入的字符串。

   • pos：當前處理到的字符位置。

   • 如果?pos == s.length()，說明已經處理完所有字符，當前的?path?就是一個完整的排列組合，將其加入?ret?中。

   • 否則，獲取當前字符?ch = s[pos]：

     • 不改變字符：

       • 將當前字符?ch?加入?path?中。

       • 遞歸調用?dfs(s, pos + 1)，處理下一個字符。

       • 回溯時，移除剛剛添加的字符?ch，恢復現場。

     • 改變字符大小寫：

       • 如果當前字符是字母（不是數字），調用?change(ch)?函數改變其大小寫。

       • 將改變后的字符加入?path?中。

       • 遞歸調用?dfs(s, pos + 1)，處理下一個字符。

       • 回溯時，移除剛剛添加的字符，恢復現場。

4. 輔助函數?change

   • 如果字符是小寫字母（a-z），將其轉換為大寫字母。

   • 如果字符是大寫字母（A-Z），將其轉換為小寫字母。

   • 返回改變后的字符。

---

代碼優化建議

1. 減少函數調用

   • 可以將?change?函數的邏輯直接嵌入到?dfs?函數中，減少函數調用的開銷。

2. 剪枝優化

   • 如果當前字符是數字，直接跳過大小寫轉換的邏輯，避免不必要的遞歸調用。

3. 代碼可讀性

   • 可以添加注釋，解釋每個步驟的作用，方便他人理解。

---

優化后的代碼

class Solution {string path; // 當前路徑vector<string> ret; // 結果集public:vector<string> letterCasePermutation(string s) {dfs(s, 0); // 從字符串的第一個字符開始深度優先搜索return ret;}void dfs(string& s, int pos) {if (pos == s.length()) { // 已經處理完所有字符ret.push_back(path); // 將當前路徑加入結果集return;}char ch = s[pos]; // 獲取當前字符// 不改變字符path.push_back(ch); // 選擇當前字符dfs(s, pos + 1); // 遞歸處理下一個字符path.pop_back(); // 回溯，撤銷選擇// 改變字符大小寫（如果是字母）if (isalpha(ch)) { // 剪枝：只處理字母char tmp = (ch >= 'a' && ch <= 'z') ? ch - 32 : ch + 32; // 改變大小寫path.push_back(tmp); // 選擇改變后的字符dfs(s, pos + 1); // 遞歸處理下一個字符path.pop_back(); // 回溯，撤銷選擇}}
};

---

代碼細節解析

1. 不改變字符

   • 將當前字符?ch?加入?path?中。

   • 遞歸處理下一個字符。

   • 回溯時，移除剛剛添加的字符?ch。

2. 改變字符大小寫

   • 如果當前字符是字母，調用?change?函數改變其大小寫。

   • 將改變后的字符加入?path?中。

   • 遞歸處理下一個字符。

   • 回溯時，移除剛剛添加的字符。

3. 剪枝優化

   • 如果當前字符是數字，直接跳過大小寫轉換的邏輯，避免不必要的遞歸調用。

---

總結

????????這段代碼的核心思想是通過 DFS 遍歷所有可能的字符大小寫排列組合，并通過回溯來恢復現場，確保每個組合都是唯一的。通過剪枝優化，可以減少不必要的遞歸調用，提高代碼效率。代碼結構清晰，邏輯簡單，適合處理這類排列組合問題。

九、526. 優美的排列 - 力扣（LeetCode）?

算法代碼：?

class Solution {bool check[16];int ret;public:int countArrangement(int n) {dfs(1, n);return ret;}void dfs(int pos, int n) {if (pos == n + 1) {ret++;return;}for (int i = 1; i <= n; i++) {if (!check[i] && (pos % i == 0 || i % pos == 0)) {check[i] = true;dfs(pos + 1, n);check[i] = false; // 恢復現場}}}
};

????????這段代碼的目的是計算給定整數?n?的所有優美排列的數量。優美排列的定義是：對于一個排列?nums，如果對于每個位置?i，nums[i]?滿足?nums[i] % i == 0?或?i % nums[i] == 0，那么這個排列就是優美的。例如，n = 2，優美排列有?[1, 2]?和?[2, 1]，輸出?2。

代碼使用了深度優先搜索（DFS）和回溯的思想來遍歷所有可能的排列，并通過剪枝優化減少不必要的遞歸調用。

---

代碼思路解析

1. 類的成員變量

   • check[16]：一個布爾數組，用于記錄數字?1?到?n?是否已經被使用。

   • ret：用于記錄優美排列的數量。

2. 主函數?countArrangement

   • 調用?dfs(1, n)?開始深度優先搜索，從位置?1?開始。

   • 返回結果?ret。

3. DFS 函數?dfs

   • pos：當前處理到的位置。

   • n：排列的長度。

   • 如果?pos == n + 1，說明已經生成了一個完整的排列，且該排列是優美的，ret++。

   • 否則，遍歷數字?1?到?n：

     • 如果數字?i?未被使用（!check[i]），并且滿足?pos % i == 0?或?i % pos == 0，則選擇該數字：

       • 將?check[i]?標記為?true，表示數字?i?已被使用。

       • 遞歸調用?dfs(pos + 1, n)，處理下一個位置。

       • 回溯時，將?check[i]?標記為?false，恢復現場。

---

代碼優化建議

1. 剪枝優化

   • 在遍歷數字?1?到?n?時，可以通過條件?pos % i == 0?或?i % pos == 0?來限制選擇范圍，避免不必要的遞歸調用。

2. 代碼可讀性

   • 可以添加注釋，解釋每個步驟的作用，方便他人理解。

---

優化后的代碼

class Solution {bool check[16]; // 記錄數字是否被使用int ret; // 優美排列的數量public:int countArrangement(int n) {dfs(1, n); // 從位置 1 開始深度優先搜索return ret;}void dfs(int pos, int n) {if (pos == n + 1) { // 已經生成了一個完整的排列ret++; // 增加優美排列的數量return;}for (int i = 1; i <= n; i++) { // 遍歷數字 1 到 nif (!check[i] && (pos % i == 0 || i % pos == 0)) { // 如果數字 i 未被使用且滿足條件check[i] = true; // 選擇數字 idfs(pos + 1, n); // 遞歸處理下一個位置check[i] = false; // 回溯，撤銷選擇}}}
};

---

代碼細節解析

1. check?數組的作用

   • check[i]?用于記錄數字?i?是否已經被使用，避免重復選擇。

2. 剪枝條件

   • pos % i == 0?或?i % pos == 0：確保選擇的數字?i?滿足優美排列的條件。

3. 回溯的恢復現場

   • 在遞歸調用結束后，通過?check[i] = false?恢復現場，確保數字?i?可以被其他排列使用。

---

總結

????????這段代碼的核心思想是通過 DFS 遍歷所有可能的排列，并通過剪枝優化減少不必要的遞歸調用。通過?check?數組記錄數字的使用情況，并通過條件?pos % i == 0?或?i % pos == 0?確保排列是優美的。代碼結構清晰，邏輯簡單，適合處理這類排列問題。

十、?51. N 皇后 - 力扣（LeetCode）

算法代碼：?

class Solution {bool checkCol[10], checkDig1[20], checkDig2[20];vector<vector<string>> ret;vector<string> path;int n;public:vector<vector<string>> solveNQueens(int _n) {n = _n;path.resize(n);for (int i = 0; i < n; i++)path[i].append(n, '.');dfs(0);return ret;}void dfs(int row) {if (row == n) {ret.push_back(path);return;}for (int col = 0; col < n; col++) // 嘗試在這??放皇后{// 剪枝if (!checkCol[col] && !checkDig1[row - col + n] &&!checkDig2[row + col]) {path[row][col] = 'Q';checkCol[col] = checkDig1[row - col + n] =checkDig2[row + col] = true;dfs(row + 1);// 恢復現場path[row][col] = '.';checkCol[col] = checkDig1[row - col + n] =checkDig2[row + col] = false;}}}
};

????????這段代碼的目的是解決?N 皇后問題，即在?n x n?的棋盤上放置?n?個皇后，使得它們互不攻擊（即任意兩個皇后不能在同一行、同一列或同一對角線上）。代碼使用了深度優先搜索（DFS）和回溯的思想來遍歷所有可能的放置方案。

---

代碼思路解析

1. 類的成員變量

   • checkCol[10]：一個布爾數組，用于記錄每一列是否已經被占用。

   • checkDig1[20]：一個布爾數組，用于記錄主對角線（從左上到右下）是否已經被占用。

   • checkDig2[20]：一個布爾數組，用于記錄副對角線（從右上到左下）是否已經被占用。

   • ret：一個二維字符串向量，用于存儲所有合法的棋盤布局。

   • path：一個字符串向量，用于存儲當前正在構建的棋盤布局。

   • n：棋盤的大小（n x n）。

2. 主函數?solveNQueens

   • 初始化?n?為輸入的?_n。

   • 初始化?path?為一個?n x n?的棋盤，所有位置初始化為?'.'。

   • 調用?dfs(0)?開始深度優先搜索，從第?0?行開始。

   • 返回結果?ret。

3. DFS 函數?dfs

   • row：當前處理到的行。

   • 如果?row == n，說明已經成功放置了?n?個皇后，將當前棋盤布局?path?加入?ret?中。

   • 否則，遍歷當前行的每一列：

     • 如果當前列?col、主對角線?row - col + n?和副對角線?row + col?都沒有被占用：

       • 在?path[row][col]?放置皇后?'Q'。

       • 標記當前列、主對角線和副對角線為已占用。

       • 遞歸調用?dfs(row + 1)，處理下一行。

       • 回溯時，移除剛剛放置的皇后，并恢復列、主對角線和副對角線的狀態。

---

代碼優化建議

1. 剪枝優化

   • 在遍歷列時，通過?checkCol、checkDig1?和?checkDig2?數組快速判斷當前位置是否可以放置皇后，避免不必要的遞歸調用。

2. 代碼可讀性

   • 可以添加注釋，解釋每個步驟的作用，方便他人理解。

---

優化后的代碼

class Solution {bool checkCol[10]; // 記錄列是否被占用bool checkDig1[20]; // 記錄主對角線是否被占用bool checkDig2[20]; // 記錄副對角線是否被占用vector<vector<string>> ret; // 所有合法的棋盤布局vector<string> path; // 當前棋盤布局int n; // 棋盤大小public:vector<vector<string>> solveNQueens(int _n) {n = _n;path.resize(n);for (int i = 0; i < n; i++) {path[i].append(n, '.'); // 初始化棋盤，所有位置為 '.'}dfs(0); // 從第 0 行開始深度優先搜索return ret;}void dfs(int row) {if (row == n) { // 已經成功放置了 n 個皇后ret.push_back(path); // 將當前棋盤布局加入結果集return;}for (int col = 0; col < n; col++) { // 遍歷當前行的每一列// 檢查當前列、主對角線和副對角線是否被占用if (!checkCol[col] && !checkDig1[row - col + n] && !checkDig2[row + col]) {path[row][col] = 'Q'; // 放置皇后checkCol[col] = checkDig1[row - col + n] = checkDig2[row + col] = true; // 標記占用dfs(row + 1); // 遞歸處理下一行// 回溯，恢復現場path[row][col] = '.';checkCol[col] = checkDig1[row - col + n] = checkDig2[row + col] = false;}}}
};

---

代碼細節解析

1. checkCol、checkDig1、checkDig2?的作用

   • checkCol[col]：記錄第?col?列是否被占用。

   • checkDig1[row - col + n]：記錄主對角線是否被占用。row - col + n?是為了避免負數索引。

   • checkDig2[row + col]：記錄副對角線是否被占用。

2. 放置皇后

   • 在?path[row][col]?放置皇后?'Q'。

   • 標記當前列、主對角線和副對角線為已占用。

3. 回溯的恢復現場

   • 移除剛剛放置的皇后?'Q'，恢復為?'.'。

   • 恢復列、主對角線和副對角線的狀態。

---

總結

????????這段代碼的核心思想是通過 DFS 遍歷所有可能的皇后放置方案，并通過回溯來恢復現場，確保每個方案都是合法的。通過?checkCol、checkDig1?和?checkDig2?數組快速判斷當前位置是否可以放置皇后，避免不必要的遞歸調用。代碼結構清晰，邏輯簡單，適合解決 N 皇后問題。

十一、36. 有效的數獨 - 力扣（LeetCode）?

?算法代碼：

class Solution {bool row[9][10] = {false};  // 記錄每一行數字是否出現bool col[9][10] = {false};  // 記錄每一列數字是否出現bool grid[3][3][10] = {false};  // 記錄每一個3x3小宮格數字是否出現public:bool isValidSudoku(vector<vector<char>>& board) {for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {if (board[i][j] != '.') {int num = board[i][j] - '0';// 檢查當前數字是否在當前行、列或小宮格中已經出現過if (row[i][num] || col[j][num] || grid[i / 3][j / 3][num]) {return false;}// 標記當前數字在當前行、列和小宮格中已經出現過row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;}}}return true;}
};

這個代碼的思路是判斷一個9x9的數獨棋盤是否有效。數獨的有效性規則是：

1. 每一行必須包含數字1-9，且不能重復。

2. 每一列必須包含數字1-9，且不能重復。

3. 每一個3x3的小宮格必須包含數字1-9，且不能重復。

代碼思路解析

1. 數據結構

   • row[9][10]：用于記錄每一行中數字1-9是否已經出現過。row[i][num]表示第i行中數字num是否已經出現過。

   • col[9][10]：用于記錄每一列中數字1-9是否已經出現過。col[j][num]表示第j列中數字num是否已經出現過。

   • grid[3][3][10]：用于記錄每一個3x3的小宮格中數字1-9是否已經出現過。grid[i/3][j/3][num]表示第(i/3, j/3)個小宮格中數字num是否已經出現過。

2. 遍歷棋盤

   • 使用雙重循環遍歷棋盤的每一個格子(i, j)。

   • 如果當前格子不是空的（即board[i][j] != '.'），則提取出數字num = board[i][j] - '0'。

3. 檢查有效性

   • 檢查當前數字num是否在當前行、當前列或當前3x3小宮格中已經出現過。如果出現過，則數獨無效，返回false。

   • 如果沒有出現過，則在row、col和grid中標記該數字已經出現過。

4. 返回結果

   • 如果遍歷完整個棋盤都沒有發現重復的數字，則數獨有效，返回true。

代碼優化建議

• 代碼已經非常簡潔高效，時間復雜度為O(1)，因為數獨棋盤的大小是固定的9x9。

• 代碼的空間復雜度也是O(1)，因為使用的輔助空間是固定的。

總結：

????????這個代碼通過使用三個輔助數組來記錄每一行、每一列和每一個3x3小宮格中數字的出現情況，從而高效地判斷數獨棋盤的有效性。代碼邏輯清晰，實現簡潔，適合解決數獨有效性問題。

十二、?37. 解數獨 - 力扣（LeetCode）

算法代碼：?

class Solution {bool row[9][10] = {false};  // 記錄每一行數字是否出現bool col[9][10] = {false};  // 記錄每一列數字是否出現bool grid[3][3][10] = {false};  // 記錄每一個3x3小宮格數字是否出現public:void solveSudoku(vector<vector<char>>& board) {// 初始化for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {if (board[i][j] != '.') {int num = board[i][j] - '0';row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;}}}dfs(board);}bool dfs(vector<vector<char>>& board) {for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {if (board[i][j] == '.') {// 嘗試填入數字1-9for (int num = 1; num <= 9; num++) {if (!row[i][num] && !col[j][num] &&!grid[i / 3][j / 3][num]) {board[i][j] = '0' + num;row[i][num] = col[j][num] =grid[i / 3][j / 3][num] = true;if (dfs(board) == true) {return true; // 找到解，直接返回}// 回溯board[i][j] = '.';row[i][num] = col[j][num] =grid[i / 3][j / 3][num] = false;}}return false; // 所有數字都嘗試過，無效}}}return true; // 所有格子都填滿，找到解}
};

這個代碼的思路是解決一個9x9的數獨問題。數獨的規則是：

1. 每一行必須包含數字1-9，且不能重復。

2. 每一列必須包含數字1-9，且不能重復。

3. 每一個3x3的小宮格必須包含數字1-9，且不能重復。

代碼思路解析

1. 數據結構

   • row[9][10]：用于記錄每一行中數字1-9是否已經出現過。row[i][num]表示第i行中數字num是否已經出現過。

   • col[9][10]：用于記錄每一列中數字1-9是否已經出現過。col[j][num]表示第j列中數字num是否已經出現過。

   • grid[3][3][10]：用于記錄每一個3x3的小宮格中數字1-9是否已經出現過。grid[i/3][j/3][num]表示第(i/3, j/3)個小宮格中數字num是否已經出現過。

2. 初始化

   • 在solveSudoku函數中，首先遍歷整個棋盤，初始化row、col和grid數組，記錄已經填入的數字。

3. 深度優先搜索（DFS）

   • dfs函數通過遞歸嘗試填充每一個空格子。

   • 對于每一個空格子(i, j)，嘗試填入數字1-9。

   • 如果填入的數字num在當前行、當前列和當前3x3小宮格中都沒有出現過，則填入該數字，并更新row、col和grid數組。

   • 遞歸調用dfs繼續填充下一個空格子。

   • 如果遞歸調用返回true，表示找到了一個有效的解，直接返回true。

   • 如果遞歸調用返回false，表示當前填入的數字num無效，需要恢復現場（即回溯），嘗試下一個數字。

4. 回溯

   • 如果所有數字1-9都嘗試過，仍然沒有找到有效的解，則返回false，表示當前路徑無效，需要回溯到上一步。

5. 終止條件

   • 如果所有格子都填滿，并且沒有沖突，則返回true，表示找到了一個有效的解。

代碼優化建議

• 代碼已經非常簡潔高效，通過回溯法系統地嘗試所有可能的數字組合，直到找到一個有效的解。

• 代碼的時間復雜度較高，因為需要嘗試所有可能的組合，但在實際應用中，由于數獨問題的約束條件較強，通常可以在合理的時間內找到解。

總結

????????這個代碼通過深度優先搜索（DFS）和回溯法系統地嘗試所有可能的數字組合，解決了數獨問題。代碼邏輯清晰，實現簡潔，適合解決數獨問題。通過遞歸和回溯，代碼能夠高效地找到數獨的有效解。

十三、?79. 單詞搜索 - 力扣（LeetCode）

?算法代碼：

class Solution {bool vis[7][7] = {false};  // 記錄每個單元格是否被訪問過int m, n;  // 網格的行數和列數int dx[4] = {0, 0, -1, 1};  // 四個方向的x偏移量int dy[4] = {1, -1, 0, 0};  // 四個方向的y偏移量public:bool exist(vector<vector<char>>& board, string word) {m = board.size(), n = board[0].size();for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (board[i][j] == word[0]) {vis[i][j] = true;  // 標記當前單元格為已訪問if (dfs(board, i, j, word, 1)) {return true;  // 找到匹配路徑}vis[i][j] = false;  // 回溯}}}return false;  // 未找到匹配路徑}bool dfs(vector<vector<char>>& board, int i, int j, string& word, int pos) {if (pos == word.size()) {return true;  // 成功匹配整個單詞}// 嘗試四個方向for (int k = 0; k < 4; k++) {int x = i + dx[k], y = j + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] &&board[x][y] == word[pos]) {vis[x][y] = true;  // 標記當前單元格為已訪問if (dfs(board, x, y, word, pos + 1)) {return true;  // 找到匹配路徑}vis[x][y] = false;  // 回溯}}return false;  // 當前路徑無效}
};

????????這個代碼的思路是解決一個經典的單詞搜索問題：在一個二維字符網格中，判斷是否存在一條路徑，使得路徑上的字符按順序連接起來恰好等于給定的單詞。路徑可以是水平或垂直相鄰的單元格，且每個單元格只能使用一次。

代碼思路解析

1. 數據結構

   • vis[7][7]：用于記錄網格中的每個單元格是否已經被訪問過。vis[i][j]表示第i行第j列的單元格是否已經被訪問。

   • m?和?n：分別表示網格的行數和列數。

   • dx[4]?和?dy[4]：用于表示四個方向（上、下、左、右）的偏移量。

2. 主函數?exist

   • 遍歷整個網格，尋找與單詞的第一個字符匹配的單元格。

   • 如果找到匹配的單元格，則標記該單元格為已訪問，并調用深度優先搜索（DFS）函數?dfs?繼續匹配剩余的字符。

   • 如果?dfs?返回?true，表示找到了匹配的路徑，直接返回?true。

   • 如果遍歷完所有可能的起始單元格都沒有找到匹配的路徑，則返回?false。

3. 深度優先搜索（DFS）函數?dfs

   • 如果當前匹配的位置?pos?等于單詞的長度，說明已經成功匹配了整個單詞，返回?true。

   • 否則，嘗試從當前單元格向四個方向（上、下、左、右）擴展，尋找下一個匹配的字符。

   • 如果擴展的單元格在網格范圍內、未被訪問過，并且字符與單詞的下一個字符匹配，則標記該單元格為已訪問，并遞歸調用?dfs。

   • 如果遞歸調用返回?true，表示找到了匹配的路徑，直接返回?true。

   • 如果遞歸調用返回?false，表示當前路徑無效，需要回溯（即恢復現場），嘗試其他方向。

4. 回溯

   • 在遞歸調用返回?false?后，需要將當前單元格的訪問狀態恢復為未訪問，以便其他路徑可以嘗試使用該單元格。

代碼優化建議

• 代碼已經非常簡潔高效，通過深度優先搜索（DFS）和回溯法系統地嘗試所有可能的路徑。

• 代碼的時間復雜度較高，因為需要嘗試所有可能的路徑，但在實際應用中，由于單詞的長度和網格的大小有限，通常可以在合理的時間內找到解。

總結

????????這個代碼通過深度優先搜索（DFS）和回溯法系統地嘗試所有可能的路徑，解決了單詞搜索問題。代碼邏輯清晰，實現簡潔，適合解決類似的二維網格搜索問題。通過遞歸和回溯，代碼能夠高效地找到匹配的路徑。

十四、?1219. 黃金礦工 - 力扣（LeetCode）

算法代碼：?

class Solution {bool vis[16][16] = {false};  // 記錄每個單元格是否被訪問過int dx[4] = {0, 0, 1, -1};  // 四個方向的x偏移量int dy[4] = {1, -1, 0, 0};  // 四個方向的y偏移量int m, n;  // 網格的行數和列數int ret = 0;  // 記錄最大黃金總量public:int getMaximumGold(vector<vector<int>>& g) {m = g.size(), n = g[0].size();for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (g[i][j]) {  // 如果當前單元格有黃金vis[i][j] = true;  // 標記當前單元格為已訪問dfs(g, i, j, g[i][j]);  // 開始DFSvis[i][j] = false;  // 回溯}}}return ret;  // 返回最大黃金總量}void dfs(vector<vector<int>>& g, int i, int j, int path) {ret = max(ret, path);  // 更新最大黃金總量for (int k = 0; k < 4; k++) {  // 嘗試四個方向int x = i + dx[k], y = j + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && g[x][y]) {vis[x][y] = true;  // 標記當前單元格為已訪問dfs(g, x, y, path + g[x][y]);  // 遞歸DFSvis[x][y] = false;  // 回溯}}}
};

????????這個代碼的思路是解決一個黃金礦工問題：在一個二維網格中，每個單元格包含一定數量的黃金（用非負整數表示），礦工可以從任意一個非零單元格出發，向上下左右四個方向移動，收集黃金。礦工不能進入黃金數量為0的單元格，也不能重復訪問同一個單元格。目標是找到一條路徑，使得礦工收集的黃金總量最大。

代碼思路解析

1. 數據結構

   • vis[16][16]：用于記錄網格中的每個單元格是否已經被訪問過。vis[i][j]表示第i行第j列的單元格是否已經被訪問。

   • dx[4]?和?dy[4]：用于表示四個方向（上、下、左、右）的偏移量。

   • m?和?n：分別表示網格的行數和列數。

   • ret：用于記錄當前找到的最大黃金總量。

2. 主函數?getMaximumGold

   • 遍歷整個網格，尋找所有非零的單元格作為起點。

   • 對于每一個非零的單元格，標記該單元格為已訪問，并調用深度優先搜索（DFS）函數?dfs?開始收集黃金。

   • 在?dfs?調用結束后，恢復該單元格的訪問狀態（回溯），以便其他路徑可以嘗試使用該單元格。

   • 最終返回?ret，即找到的最大黃金總量。

3. 深度優先搜索（DFS）函數?dfs

   • 更新當前路徑的黃金總量?path，并與?ret?比較，更新?ret?為較大值。

   • 嘗試從當前單元格向四個方向（上、下、左、右）擴展，尋找下一個可以收集黃金的單元格。

   • 如果擴展的單元格在網格范圍內、未被訪問過，并且黃金數量不為0，則標記該單元格為已訪問，并遞歸調用?dfs。

   • 在遞歸調用結束后，恢復該單元格的訪問狀態（回溯），以便其他路徑可以嘗試使用該單元格。

4. 回溯

   • 在遞歸調用結束后，需要將當前單元格的訪問狀態恢復為未訪問，以便其他路徑可以嘗試使用該單元格。

代碼優化建議

• 代碼已經非常簡潔高效，通過深度優先搜索（DFS）和回溯法系統地嘗試所有可能的路徑。

• 代碼的時間復雜度較高，因為需要嘗試所有可能的路徑，但在實際應用中，由于網格的大小和黃金數量的限制，通常可以在合理的時間內找到解。

總結

????????這個代碼通過深度優先搜索（DFS）和回溯法系統地嘗試所有可能的路徑，解決了黃金礦工問題。代碼邏輯清晰，實現簡潔，適合解決類似的二維網格搜索問題。通過遞歸和回溯，代碼能夠高效地找到收集黃金的最大路徑。

十五、980. 不同路徑 III - 力扣（LeetCode）?

算法代碼：

class Solution {bool vis[21][21] = {false};  // 記錄每個單元格是否被訪問過int dx[4] = {1, -1, 0, 0};  // 四個方向的x偏移量int dy[4] = {0, 0, 1, -1};  // 四個方向的y偏移量int ret = 0;  // 記錄滿足條件的路徑數量int m, n, step;  // 網格的行數、列數和需要經過的總步數public:int uniquePathsIII(vector<vector<int>>& grid) {m = grid.size(), n = grid[0].size();int bx = 0, by = 0;  // 起點的位置step = 0;  // 初始化需要經過的步數for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 0) {step++;  // 統計空單元格的數量} else if (grid[i][j] == 1) {bx = i;  // 記錄起點的行by = j;  // 記錄起點的列}}}step += 2;  // 包括起點和終點vis[bx][by] = true;  // 標記起點為已訪問dfs(grid, bx, by, 1);  // 開始DFSreturn ret;  // 返回滿足條件的路徑數量}void dfs(vector<vector<int>>& grid, int i, int j, int count) {if (grid[i][j] == 2) {  // 如果當前單元格是終點if (count == step) {  // 判斷是否經過所有空單元格ret++;  // 滿足條件，路徑數量加1}return;}for (int k = 0; k < 4; k++) {  // 嘗試四個方向int x = i + dx[k], y = j + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] &&grid[x][y] != -1) {  // 檢查是否合法vis[x][y] = true;  // 標記當前單元格為已訪問dfs(grid, x, y, count + 1);  // 遞歸DFSvis[x][y] = false;  // 回溯}}}
};

?這個代碼的思路是解決一個獨特路徑問題 III：在一個二維網格中，每個單元格可能包含以下值：

• 0：表示空單元格，可以通過。

• 1：表示起點。

• 2：表示終點。

• -1：表示障礙物，不能通過。

????????目標是找到從起點到終點的所有路徑，要求路徑必須經過所有的空單元格（0），并且每個單元格只能訪問一次。

代碼思路解析

1. 數據結構

   • vis[21][21]：用于記錄網格中的每個單元格是否已經被訪問過。vis[i][j]表示第i行第j列的單元格是否已經被訪問。

   • dx[4]?和?dy[4]：用于表示四個方向（上、下、左、右）的偏移量。

   • m?和?n：分別表示網格的行數和列數。

   • step：表示需要經過的空單元格數量（包括起點和終點）。

   • ret：用于記錄滿足條件的路徑數量。

2. 主函數?uniquePathsIII

   • 遍歷整個網格，統計空單元格的數量（0），并找到起點的位置（1）。

   • 將需要經過的總步數?step?設置為空單元格數量加2（包括起點和終點）。

   • 標記起點為已訪問，并調用深度優先搜索（DFS）函數?dfs?開始搜索路徑。

   • 最終返回?ret，即滿足條件的路徑數量。

3. 深度優先搜索（DFS）函數?dfs

   • 如果當前單元格是終點（2），并且已經經過的步數?count?等于?step，則說明找到了一條合法路徑，ret?加1。

   • 否則，嘗試從當前單元格向四個方向（上、下、左、右）擴展，尋找下一個可以訪問的單元格。

   • 如果擴展的單元格在網格范圍內、未被訪問過，并且不是障礙物（-1），則標記該單元格為已訪問，并遞歸調用?dfs。

   • 在遞歸調用結束后，恢復該單元格的訪問狀態（回溯），以便其他路徑可以嘗試使用該單元格。

4. 回溯

   • 在遞歸調用結束后，需要將當前單元格的訪問狀態恢復為未訪問，以便其他路徑可以嘗試使用該單元格。

代碼優化建議

• 代碼已經非常簡潔高效，通過深度優先搜索（DFS）和回溯法系統地嘗試所有可能的路徑。

• 代碼的時間復雜度較高，因為需要嘗試所有可能的路徑，但在實際應用中，由于網格的大小和路徑的限制，通常可以在合理的時間內找到解。

總結

????????這個代碼通過深度優先搜索（DFS）和回溯法系統地嘗試所有可能的路徑，解決了獨特路徑問題 III。代碼邏輯清晰，實現簡潔，適合解決類似的二維網格搜索問題。通過遞歸和回溯，代碼能夠高效地找到滿足條件的路徑數量。