---

---

一、引言

回溯算法是一種利用遞歸解決搜索問題的常見方法，它在多個(gè)編程題型中展現(xiàn)出獨(dú)特的優(yōu)勢。無論是組合問題、分割問題、子集問題，還是排列、棋盤問題，回溯算法的核心都是在構(gòu)建路徑的同時(shí)，動(dòng)態(tài)地選擇、撤銷操作，最終完成一個(gè)全面的搜索。本系列文章將通過15道經(jīng)典的LeetCode題目，用Go語言實(shí)現(xiàn)并深入解析回溯算法的設(shè)計(jì)模式，幫助您系統(tǒng)化掌握回溯算法在各類問題中的應(yīng)用。

二、回溯算法的核心概念

在學(xué)習(xí)回溯算法前，理解其核心概念非常重要。在所有回溯算法的實(shí)現(xiàn)中，都離不開以下幾個(gè)關(guān)鍵部分：

1. 遞歸與回溯的關(guān)系：

   • 回溯算法是一種基于遞歸的搜索算法。遞歸逐層深入，構(gòu)建一個(gè)狀態(tài)空間樹（即遞歸樹），每層遞歸都代表決策路徑的一個(gè)選擇。
   • 一旦遞歸到達(dá)終止條件，回溯將會(huì)逐層返回，撤銷不符合條件的選擇，形成“退一步再試其他路徑”的機(jī)制。

2. 終止條件：

   • 每個(gè)回溯算法都有一個(gè)明確的終止條件，當(dāng)條件滿足時(shí)，算法會(huì)返回或?qū)⒔Y(jié)果存儲(chǔ)下來。典型的例子包括達(dá)成某個(gè)組合的長度、和為目標(biāo)值、或者生成所有排列。

3. 結(jié)果收集條件：

   • 在遞歸過程中，只有滿足條件的路徑才會(huì)被收集。條件可能是固定的組合大小、具體的和、路徑的合法性等。
   • 例如在N皇后問題中，結(jié)果收集條件是所有皇后均放置完畢且不沖突。

4. 去重邏輯：

   • 對于一些包含重復(fù)元素的問題（如排列或子集問題），去重是關(guān)鍵。常用的去重策略包括提前排序和跳過相同元素。

5. 遞歸控制：

   • 循環(huán)順序決定了遞歸樹的遍歷路徑；遞歸順序決定了函數(shù)返回的優(yōu)先順序。一般來說，組合問題在遞歸內(nèi)部通過for循環(huán)控制選擇的順序，而排列問題則會(huì)基于深度優(yōu)先搜索實(shí)現(xiàn)路徑的構(gòu)建。

6. 回溯算法整體框架流程圖

在接下來的章節(jié)中，我們將具體分析這15道力扣題目，深入解讀回溯算法在不同問題場景下的應(yīng)用與技巧。

---

三、組合問題

組合問題的特點(diǎn)是每個(gè)解都是一個(gè)子集或集合，且不要求集合中的元素有順序性。下面是具體題目實(shí)現(xiàn)與解析。

---

1. LeetCode 77. 組合

題目分析：
題目要求從1到n中選出k個(gè)數(shù)字的組合。通過遞歸逐步構(gòu)建組合，若達(dá)到所需長度則收集結(jié)果。此題中的路徑長度就是終止條件。

組合問題的回溯流程

Go語言實(shí)現(xiàn)：

func combine(n int, k int) [][]int {var res [][]int        // 存儲(chǔ)最終結(jié)果var path []int         // 存儲(chǔ)當(dāng)前組合路徑var backTrack func(s int)  // 定義回溯函數(shù)backTrack = func(s int) {// 當(dāng)路徑長度達(dá)到k時(shí)，保存當(dāng)前路徑并返回if len(path) == k {temp := make([]int, k)copy(temp, path)res = append(res, temp)return}// 從s開始選擇元素for i := s; i <= n; i++ {path = append(path, i)    // 選擇元素i加入路徑backTrack(i + 1)          // 遞歸調(diào)用下一層path = path[:len(path)-1] // 撤銷選擇}}backTrack(1)  // 從1開始遞歸return res
}

詳細(xì)解讀：

1. 遞歸與回溯：backTrack函數(shù)是遞歸的核心，每次選擇后續(xù)數(shù)字中的一個(gè)加入路徑。
2. 終止條件：當(dāng)路徑長度等于k時(shí)，保存當(dāng)前路徑（組合）。
3. 結(jié)果收集條件：在路徑長度等于k時(shí)，將組合結(jié)果收集到res中。
4. 去重邏輯：題目不允許重復(fù)選擇，因此每次遞歸從s到n，每層遞歸僅選擇一次。
5. 遞歸控制：循環(huán)順序由s至n，確保每次遞歸的元素都是唯一且不重復(fù)的。

---

2. LeetCode 216. 組合總和III

題目分析：
從數(shù)字1-9中選出k個(gè)數(shù)字，使它們的和等于目標(biāo)值n。在組合過程中需保持路徑長度和總和滿足條件。

Go語言實(shí)現(xiàn)：

func combinationSum(k int, n int) [][]int {var res [][]intvar path []intvar sum int          // 當(dāng)前路徑的總和var backTrack func(s int)backTrack = func(s int) {// 若路徑長度和總和同時(shí)滿足要求，保存結(jié)果if len(path) == k && sum == n {temp := make([]int, k)copy(temp, path)res = append(res, temp)return}// 剪枝條件：路徑長度超過k或總和超過n時(shí)直接返回if len(path) > k || sum > n {return}// 從s到9逐一選擇元素for i := s; i <= 9; i++ {path = append(path, i)    // 選擇i加入路徑sum += i                  // 更新路徑總和backTrack(i + 1)          // 遞歸調(diào)用下一層sum -= i                  // 撤銷選擇ipath = path[:len(path)-1] // 回溯到上層狀態(tài)}}backTrack(1)return res
}

詳細(xì)解讀：

1. 終止條件：當(dāng)路徑長度達(dá)到k且總和等于n時(shí)，保存組合。
2. 結(jié)果收集條件：在滿足k和n的條件時(shí)，記錄路徑。
3. 去重邏輯：依次遞歸選取1-9的數(shù)字，通過s遞歸參數(shù)限制重復(fù)選擇。
4. 剪枝條件：提前檢查路徑長度和總和，避免無效遞歸。
5. 遞歸控制：使用s至9的遞增順序，保證路徑中無重復(fù)數(shù)字。

---

3. LeetCode 17. 電話號(hào)碼的字母組合

題目分析：
給定一個(gè)僅包含數(shù)字2-9的字符串，返回所有它能表示的字母組合。每個(gè)數(shù)字代表一組字母，要求構(gòu)造出所有可能的字母排列組合。

思路解析：
這道題的關(guān)鍵在于逐層遞歸處理每個(gè)數(shù)字對應(yīng)的字母組合，并在滿足條件后將路徑保存下來。遞歸深度等于數(shù)字長度，而每層遞歸中的循環(huán)則負(fù)責(zé)選擇不同的字母。通過回溯刪除不符合的路徑，從而覆蓋所有組合。

Go語言實(shí)現(xiàn)：

func letterCombinations(digits string) []string {letters := map[byte][]byte{'2': {'a', 'b', 'c'},'3': {'d', 'e', 'f'},'4': {'g', 'h', 'i'},'5': {'j', 'k', 'l'},'6': {'m', 'n', 'o'},'7': {'p', 'q', 'r', 's'},'8': {'t', 'u', 'v'},'9': {'w', 'x', 'y', 'z'},}var res []stringvar path []bytel := len(digits)if l == 0 {return res}var backTrack func(s int)backTrack = func(s int) {// 當(dāng)路徑長度達(dá)到數(shù)字串長度時(shí)，將路徑轉(zhuǎn)換為字符串并保存if s == l {res = append(res, string(path))return}// 選擇當(dāng)前數(shù)字對應(yīng)的每個(gè)字母for _, ch := range letters[digits[s]] {path = append(path, ch)   // 選擇一個(gè)字母backTrack(s + 1)          // 遞歸到下一數(shù)字path = path[:len(path)-1] // 撤銷選擇，回溯到上層狀態(tài)}}backTrack(0)return res
}

詳細(xì)解讀：

1. 終止條件：

   • 當(dāng)path長度與digits長度一致時(shí)，將當(dāng)前路徑拼接成字符串，并存入結(jié)果集。

2. 結(jié)果收集條件：

   • 在path長度等于digits時(shí)，收集路徑。

3. 去重邏輯：

   • 每個(gè)數(shù)字的字母都是固定且不重復(fù)的，因此不需要特殊去重處理。

4. 遞歸控制：

   • 外層遞歸控制數(shù)字索引；內(nèi)層循環(huán)處理每個(gè)數(shù)字對應(yīng)的字母組合。

---

4. LeetCode 39. 組合總和

題目分析：
從給定的正整數(shù)數(shù)組candidates中找到所有可能的組合，使得組合中的元素之和等于目標(biāo)值target。數(shù)組中元素可以重復(fù)使用。

思路解析：
為保證路徑中的數(shù)字和達(dá)到target且避免重復(fù)組合，需要在遞歸中控制好路徑的總和。每層遞歸會(huì)從當(dāng)前位置到數(shù)組結(jié)尾進(jìn)行選擇，允許重復(fù)選擇。若總和超出目標(biāo)值target，立即停止遞歸。

Go語言實(shí)現(xiàn)：

func combinationSum(candidates []int, target int) [][]int {var res [][]intvar path []intvar sum intvar backTrack func(s int)backTrack = func(s int) {// 當(dāng)總和超出目標(biāo)時(shí)，停止遞歸if sum > target {return}// 當(dāng)總和達(dá)到目標(biāo)時(shí)，記錄當(dāng)前路徑if sum == target {temp := make([]int, len(path))copy(temp, path)res = append(res, temp)return}// 從s到數(shù)組末尾嘗試每個(gè)候選數(shù)for i := s; i < len(candidates); i++ {path = append(path, candidates[i]) // 選擇候選數(shù)sum += candidates[i]               // 更新路徑總和backTrack(i)                       // 遞歸允許重復(fù)選擇sum -= candidates[i]               // 回溯到上層path = path[:len(path)-1]          // 撤銷選擇}}backTrack(0)return res
}

詳細(xì)解讀：

1. 終止條件：

   • 總和等于目標(biāo)target時(shí)，將路徑存入結(jié)果集；
   • 若總和超過target，則提前返回，避免無效遞歸。

2. 結(jié)果收集條件：

   • 在sum == target時(shí)，保存路徑。

3. 去重邏輯：

   • 候選元素位置遞增，無需額外去重。

4. 遞歸控制：

   • 每層遞歸從s開始，允許同元素在遞歸中多次選擇，形成重復(fù)組合的路徑。

---

5. LeetCode 40. 組合總和 II

題目分析：
本題和上一題類似，但要求組合中的每個(gè)數(shù)字只能使用一次，并且不能有重復(fù)組合。即在數(shù)組中選取不同組合使其和為target，每個(gè)組合內(nèi)部元素可以重復(fù)，但組合間不能有重復(fù)。

思路解析：
通過提前對數(shù)組排序以及遞歸中的剪枝處理來去重，從而確保不會(huì)重復(fù)選擇同一個(gè)元素。每層遞歸的選擇會(huì)跳過重復(fù)元素，避免組合重復(fù)。

Go語言實(shí)現(xiàn)：

func combinationSum2(candidates []int, target int) [][]int {var res [][]intvar path []intvar sum intsort.Ints(candidates)     // 預(yù)排序以方便去重var backTrack func(s int)backTrack = func(s int) {if sum == target {temp := make([]int, len(path))copy(temp, path)res = append(res, temp)return}if sum > target {return}for i := s; i < len(candidates); i++ {// 去重：若當(dāng)前數(shù)等于上一個(gè)，且在同一層遞歸中未被選過，則跳過if i > s && candidates[i] == candidates[i-1] {continue}path = append(path, candidates[i]) // 選擇候選數(shù)sum += candidates[i]               // 更新路徑總和backTrack(i + 1)                   // 從下一個(gè)元素遞歸sum -= candidates[i]               // 回溯到上層path = path[:len(path)-1]          // 撤銷選擇}}backTrack(0)return res
}

詳細(xì)解讀：

1. 終止條件：

   • 當(dāng)sum等于target時(shí)，將路徑加入結(jié)果集；
   • 當(dāng)sum超過target時(shí)，提前返回，停止當(dāng)前遞歸。

2. 結(jié)果收集條件：

   • 在sum == target時(shí)，保存路徑。

3. 去重邏輯：

   • 排序后在循環(huán)中跳過重復(fù)元素candidates[i] == candidates[i-1]，保證每個(gè)組合的唯一性。

4. 遞歸控制：

   • 每層遞歸選擇當(dāng)前或后續(xù)元素，確保每個(gè)數(shù)只能選一次并避免重復(fù)組合。

---

小結(jié)

在組合問題中，回溯算法的核心在于控制組合生成的方式和路徑。結(jié)合剪枝、去重等方法，不僅能提高算法效率，還能避免重復(fù)組合的生成。在實(shí)現(xiàn)上，終止條件和結(jié)果收集條件的正確設(shè)置十分關(guān)鍵。此外，通過for循環(huán)控制遞歸深度和選擇范圍，能夠生成符合題目要求的組合解。

---

四、分割問題

分割問題的核心在于將給定的字符串分解成多個(gè)滿足條件的部分。通過回溯逐層遞歸地探索各個(gè)可能的分割點(diǎn)，確保每一層遞歸選擇的部分滿足題目要求。以下是具體題目的解析與實(shí)現(xiàn)。

---

6. LeetCode 131. 分割回文串

題目分析：
給定一個(gè)字符串s，要求將其分割，使每個(gè)分割后的子串都是回文串。返回所有可能的回文分割方案。

思路解析：
該題目需要使用回溯和分治的思想，逐層遞歸探索字符串的每一個(gè)分割位置。對于每一個(gè)可能的分割點(diǎn)，檢查其是否是回文串，如果是，則繼續(xù)遞歸剩下的部分；否則跳過。

Go語言實(shí)現(xiàn)：

// 輔助函數(shù)：檢查是否為回文串
func isPalindrome(s string) bool {for l, r := 0, len(s)-1; l < r; l, r = l+1, r-1 {if s[l] != s[r] {return false}}return true
}func partition(s string) [][]string {var res [][]stringvar path []stringl := len(s)var backTrack func(start int)backTrack = func(start int) {// 終止條件：到達(dá)字符串末尾時(shí)，記錄當(dāng)前分割路徑if start == l {temp := make([]string, len(path))copy(temp, path)res = append(res, temp)return}// 從start位置開始嘗試分割每個(gè)可能的子串for i := start; i < l; i++ {if !isPalindrome(s[start : i+1]) { // 判斷子串是否為回文continue}path = append(path, s[start:i+1]) // 選擇當(dāng)前回文子串backTrack(i + 1)                  // 遞歸處理剩余部分path = path[:len(path)-1]         // 撤銷選擇，回溯到上層}}backTrack(0)return res
}

詳細(xì)解讀：

1. 終止條件：

   • 當(dāng)遍歷到字符串的末尾時(shí)（start == l），將當(dāng)前路徑path存入結(jié)果集中。

2. 結(jié)果收集條件：

   • 若當(dāng)前分割路徑到達(dá)字符串末尾，將其存入結(jié)果集。

3. 去重邏輯：

   • 本題不存在重復(fù)組合的問題，因?yàn)槊看芜x擇都基于字符串的索引位置，保證了結(jié)果的唯一性。

4. 遞歸控制：

   • 通過for循環(huán)控制每一層的分割起始位置，逐層向后分割，確保各個(gè)分割部分為回文串。

---

7. LeetCode 93. 復(fù)原IP地址

題目分析：
給定一個(gè)只含數(shù)字的字符串，要求將其復(fù)原成可能的有效IP地址。IP地址由四個(gè)十進(jìn)制部分組成，每部分在0到255之間，且不能包含前導(dǎo)零。

思路解析：
該題目使用回溯嘗試將字符串分割為4部分，每部分代表IP地址的一個(gè)段。需要特別注意的是，IP地址每部分的范圍限定為0-255，且不能有前導(dǎo)零。遞歸過程中，當(dāng)達(dá)到4段且字符串用完即為有效分割。

Go語言實(shí)現(xiàn)：

import "strconv"// 輔助函數(shù)：檢查是否為有效IP地址段
func isValidSegment(s string) bool {if len(s) == 0 || (len(s) > 1 && s[0] == '0') {return false}num, _ := strconv.Atoi(s)return num >= 0 && num <= 255
}func restoreIpAddresses(s string) []string {var res []stringvar path []stringl := len(s)var backTrack func(start int)backTrack = func(start int) {// 當(dāng)path有4段且字符串用完，表示找到一個(gè)有效IPif len(path) == 4 && start == l {res = append(res, path[0]+"."+path[1]+"."+path[2]+"."+path[3])return}// 若path已達(dá)4段但未用完字符串，提前結(jié)束if len(path) == 4 {return}// 遍歷每個(gè)可能的分割點(diǎn)，每段最多3位for i := start; i < min(start+3, l); i++ {segment := s[start : i+1]if !isValidSegment(segment) {continue}path = append(path, segment) // 選擇有效IP段backTrack(i + 1)             // 遞歸處理剩余字符串path = path[:len(path)-1]    // 回溯，撤銷選擇}}backTrack(0)return res
}func min(a, b int) int {if a < b {return a}return b
}

詳細(xì)解讀：

1. 終止條件：

   • 當(dāng)path長度等于4段且字符串用完時(shí)，表示找到一個(gè)有效的IP地址，將其存入結(jié)果集。
   • 若path已達(dá)4段，但未用完字符串，則提前結(jié)束當(dāng)前路徑。

2. 結(jié)果收集條件：

   • 在滿足4段IP和完整字符串條件時(shí)，將路徑加入結(jié)果集。

3. 去重邏輯：

   • 本題不存在重復(fù)組合，因?yàn)槊慷畏指顑H對應(yīng)一個(gè)合法的IP段。

4. 遞歸控制：

   • 遞歸逐層分割，每層遞歸最多選擇3個(gè)字符作為IP地址段，避免超過有效長度。

---

小結(jié)

分割問題的回溯算法設(shè)計(jì)關(guān)鍵在于：

1. 分割點(diǎn)的選擇與遞歸控制：每一層遞歸都嘗試不同的分割點(diǎn)，以探索多種可能的路徑。
2. 有效性校驗(yàn)：分割后的子串必須符合特定條件（如回文或IP段的范圍），在遞歸選擇時(shí)及時(shí)進(jìn)行校驗(yàn)，避免無效路徑。
3. 路徑收集條件：只有滿足條件的路徑（如達(dá)到分割段數(shù)）才會(huì)收集到最終結(jié)果集中。

---

五、子集問題

子集問題需要在給定數(shù)組中找到所有可能的子集組合。這里的關(guān)鍵是每個(gè)元素的選擇與不選擇，形成不同的組合方案。子集問題的核心思路是通過遞歸回溯，逐步生成所有可能的子集組合。

---

8. LeetCode 78. 子集

題目分析：
給定一個(gè)不含重復(fù)元素的整數(shù)數(shù)組nums，求所有的子集（包括空集）。該題要求返回所有可能的子集，因此每個(gè)元素都有加入和不加入當(dāng)前組合的兩種選擇。

思路解析：
通過遞歸遍歷數(shù)組，分別處理每個(gè)元素的“加入”和“不加入”操作，逐步構(gòu)建出所有的子集。由于子集中沒有順序要求，遞歸中可以按順序加入新元素，不必考慮排列順序。

Go語言實(shí)現(xiàn)：

func subsets(nums []int) [][]int {var res [][]intvar path []intl := len(nums)var backTrack func(start int)backTrack = func(start int) {// 將當(dāng)前路徑加入結(jié)果集中temp := make([]int, len(path))copy(temp, path)res = append(res, temp)// 從當(dāng)前元素開始，遞歸構(gòu)建子集for i := start; i < l; i++ {path = append(path, nums[i]) // 選擇當(dāng)前元素backTrack(i + 1)             // 遞歸生成后續(xù)子集path = path[:len(path)-1]    // 撤銷選擇，回溯}}backTrack(0)return res
}

詳細(xì)解讀：

1. 終止條件：

   • 每次遞歸調(diào)用都會(huì)將當(dāng)前路徑加入結(jié)果集，無需特定終止條件。

2. 結(jié)果收集條件：

   • 在每層遞歸中將路徑path加入res，表示當(dāng)前組合就是一個(gè)子集。

3. 去重邏輯：

   • 因?yàn)閿?shù)組不包含重復(fù)元素，每次遞歸中不需要去重操作。

4. 遞歸控制：

   • 每層遞歸的for循環(huán)從當(dāng)前位置開始，確保每個(gè)組合無重復(fù)順序，形成不同的子集。

---

9. LeetCode 90. 子集 II

題目分析：
與上一題不同的是，給定的數(shù)組nums中包含重復(fù)元素，求所有可能的子集。由于存在重復(fù)元素，需要確保相同的元素不會(huì)生成重復(fù)的子集。

思路解析：
為避免重復(fù)組合，首先對數(shù)組進(jìn)行排序，這樣在遞歸過程中可以跳過重復(fù)的元素。若當(dāng)前元素與前一個(gè)元素相同，且前一個(gè)元素未被選擇，則跳過當(dāng)前元素，確保唯一性。

Go語言實(shí)現(xiàn)：

import "sort"func subsetsWithDup(nums []int) [][]int {var res [][]intvar path []intsort.Ints(nums) // 預(yù)排序以便去重var backTrack func(start int)backTrack = func(start int) {// 保存當(dāng)前路徑作為子集temp := make([]int, len(path))copy(temp, path)res = append(res, temp)// 從start位置開始遞歸for i := start; i < len(nums); i++ {// 去重：若當(dāng)前元素等于上一個(gè)且未被選過，則跳過if i > start && nums[i] == nums[i-1] {continue}path = append(path, nums[i]) // 選擇當(dāng)前元素backTrack(i + 1)             // 遞歸到下一個(gè)位置path = path[:len(path)-1]    // 回溯，撤銷選擇}}backTrack(0)return res
}

詳細(xì)解讀：

1. 終止條件：

   • 每次遞歸調(diào)用都會(huì)將當(dāng)前路徑加入結(jié)果集，形成一個(gè)子集。

2. 結(jié)果收集條件：

   • 在每層遞歸中將當(dāng)前路徑path加入res，即收集當(dāng)前形成的子集。

3. 去重邏輯：

   • 數(shù)組排序后，利用條件if i > start && nums[i] == nums[i-1]跳過重復(fù)的元素，防止生成重復(fù)子集。

4. 遞歸控制：

   • 每層遞歸的for循環(huán)從start位置開始，以保證子集生成的順序不變且不重復(fù)。

---

小結(jié)

子集問題通過遞歸生成所有組合，關(guān)鍵在于：

1. 選擇與不選擇的決策：每個(gè)元素都面臨“加入”或“不加入”的選擇，這構(gòu)成了回溯遞歸的基本框架。
2. 去重邏輯的實(shí)現(xiàn)：在含重復(fù)元素的子集問題中，提前排序并在遞歸過程中跳過相同元素，確保生成的子集組合唯一。
3. 路徑收集的時(shí)機(jī)：每個(gè)遞歸點(diǎn)的路徑即為一個(gè)子集，因此在每次遞歸時(shí)都保存當(dāng)前路徑。

通過對比78和90兩道題，可以看到在處理重復(fù)元素和去重邏輯上的不同應(yīng)用。接下來我們將進(jìn)入排列問題的分析與實(shí)現(xiàn)。

六、排列問題

排列問題要求對給定數(shù)組生成所有可能的排列，特別是每個(gè)排列中元素的順序必須唯一。排列問題的核心思路是使用遞歸回溯，從給定數(shù)組逐個(gè)選擇元素加入路徑，直到路徑長度等于數(shù)組長度時(shí)生成一個(gè)排列。

---

10. LeetCode 46. 全排列

題目分析：
給定一個(gè)不含重復(fù)數(shù)字的數(shù)組nums，要求返回其所有可能的排列。該題與組合和子集問題的區(qū)別在于，排列中的順序不同會(huì)產(chǎn)生不同的排列結(jié)果，因此遞歸過程中需要處理元素的交換和位置選擇。

思路解析：
使用回溯法，在每層遞歸中按順序選擇一個(gè)未使用的元素加入路徑，直到路徑長度與數(shù)組長度一致。每次遞歸結(jié)束后回退選擇，恢復(fù)現(xiàn)場，確保所有位置都被遍歷到。

Go語言實(shí)現(xiàn)：

func permute(nums []int) [][]int {var res [][]intvar path []intl := len(nums)used := make(map[int]bool) // 記錄每個(gè)元素是否已在當(dāng)前排列中使用var backTrack func()backTrack = func() {// 當(dāng)路徑長度等于數(shù)組長度時(shí)，保存當(dāng)前排列if len(path) == l {temp := make([]int, l)copy(temp, path)res = append(res, temp)return}// 遍歷每個(gè)元素for i := 0; i < l; i++ {if used[nums[i]] {continue // 跳過已使用的元素}used[nums[i]] = true       // 標(biāo)記元素已使用path = append(path, nums[i]) // 選擇當(dāng)前元素backTrack()                 // 遞歸生成后續(xù)排列path = path[:len(path)-1]   // 撤銷選擇，回溯used[nums[i]] = false       // 取消標(biāo)記}}backTrack()return res
}

詳細(xì)解讀：

1. 終止條件：

   • 當(dāng)路徑長度等于數(shù)組長度時(shí)，表示形成了一個(gè)完整的排列，加入結(jié)果集。

2. 結(jié)果收集條件：

   • 在遞歸層次達(dá)到數(shù)組長度時(shí)，將當(dāng)前路徑path加入結(jié)果集。

3. 去重邏輯：

   • 每次遞歸中使用used字典標(biāo)記每個(gè)元素是否已在當(dāng)前排列路徑中，避免重復(fù)選擇。

4. 遞歸控制：

   • for循環(huán)遍歷數(shù)組中每一個(gè)元素，并在遞歸中控制元素選擇與撤銷，從而生成所有排列。

---

11. LeetCode 47. 全排列 II

題目分析：
與前一題不同的是，給定的數(shù)組nums中可能包含重復(fù)元素，要求生成的排列中不應(yīng)有重復(fù)項(xiàng)。因此在遞歸中需要確保相同的元素不會(huì)導(dǎo)致重復(fù)排列。

思路解析：
先對數(shù)組排序，這樣在遞歸時(shí)可以通過判斷跳過相同元素以去重。此外，若前一個(gè)相同的元素未被選過，則當(dāng)前元素也不能選，確保每層遞歸中生成的排列唯一。

Go語言實(shí)現(xiàn)：

import "sort"func permuteUnique(nums []int) [][]int {var res [][]intvar path []intl := len(nums)used := make([]bool, l) // 記錄每個(gè)位置的元素是否已被選中sort.Ints(nums)         // 排序以便去重var backTrack func()backTrack = func() {// 當(dāng)路徑長度等于數(shù)組長度時(shí)，保存當(dāng)前排列if len(path) == l {temp := make([]int, l)copy(temp, path)res = append(res, temp)return}// 遍歷每個(gè)元素for i := 0; i < l; i++ {// 去重邏輯：跳過重復(fù)元素if i > 0 && nums[i] == nums[i-1] && !used[i-1] {continue}if used[i] {continue}used[i] = true              // 標(biāo)記元素已使用path = append(path, nums[i]) // 選擇當(dāng)前元素backTrack()                 // 遞歸生成后續(xù)排列path = path[:len(path)-1]   // 撤銷選擇，回溯used[i] = false             // 取消標(biāo)記}}backTrack()return res
}

詳細(xì)解讀：

1. 終止條件：

   • 路徑長度等于數(shù)組長度時(shí)，生成一個(gè)完整排列，加入結(jié)果集。

2. 結(jié)果收集條件：

   • 在遞歸層次等于數(shù)組長度時(shí)，將當(dāng)前排列路徑path加入res。

3. 去重邏輯：

   • 排序后，跳過已選過的相同元素（nums[i] == nums[i-1] && !used[i-1]），避免重復(fù)排列的生成，去重操作僅作用于當(dāng)前遞歸層。

4. 遞歸控制：

   • for循環(huán)控制排列的順序，used數(shù)組記錄每個(gè)元素的使用狀態(tài)，并在遞歸和回溯中交替使用。

---

小結(jié)

在排列問題中，通過逐層遞歸生成所有可能的排列，遞歸過程中確保唯一性至關(guān)重要：

1. 路徑收集條件：遞歸深度等于數(shù)組長度時(shí)表示一個(gè)完整的排列，及時(shí)收集。
2. 去重策略的應(yīng)用：排序和跳過相同元素的邏輯可有效去除重復(fù)排列。
3. 遞歸結(jié)構(gòu)：每層遞歸中控制元素的選擇、加入、撤銷，通過遞歸的深度優(yōu)先遍歷實(shí)現(xiàn)所有排列的組合。

在比較46和47題時(shí)可以看到，包含重復(fù)元素的排列需要在遞歸中加入去重策略，確保排列唯一性。接下來將進(jìn)入棋盤問題的解析與實(shí)現(xiàn)。

---

七、棋盤問題

棋盤問題通常涉及在棋盤上放置棋子（如皇后或數(shù)字），滿足特定規(guī)則。回溯算法在棋盤問題中廣泛應(yīng)用，因?yàn)榛厮菽軌蛴行У靥幚砥遄拥姆胖?、撤回以及合法性檢測，從而找到所有可能的棋盤解法。

---

12. LeetCode 51. N皇后

題目分析：
在n x n的棋盤上放置n個(gè)皇后，使得任意兩個(gè)皇后都不在同一行、同一列或同一條對角線上。要求返回所有可能的放置方案。

思路解析：
該題可以通過回溯解決，每次遞歸在棋盤的某一行放置皇后，然后遞歸到下一行，檢查每個(gè)位置是否會(huì)與已放置的皇后沖突。若沖突則跳過該位置，若無沖突則放置皇后并繼續(xù)遞歸。遞歸完成后通過回溯撤銷選擇，以便探索下一種可能方案。

N皇后問題的棋盤遞歸流程

Go語言實(shí)現(xiàn)：

func solveNQueens(n int) [][]string {var res [][]stringboard := make([][]string, n) // 創(chuàng)建棋盤for i := range board {board[i] = make([]string, n)for j := range board[i] {board[i][j] = "." // 初始化棋盤為空位}}// 檢查當(dāng)前放置是否會(huì)與已有皇后沖突var isValid func(row, col int) boolisValid = func(row, col int) bool {// 檢查列是否有皇后for i := 0; i < row; i++ {if board[i][col] == "Q" {return false}}// 檢查左上對角線是否有皇后for i, j := row-1, col-1; i >= 0 && j >= 0; i, j = i-1, j-1 {if board[i][j] == "Q" {return false}}// 檢查右上對角線是否有皇后for i, j := row-1, col+1; i >= 0 && j < n; i, j = i-1, j+1 {if board[i][j] == "Q" {return false}}return true}// 將當(dāng)前棋盤狀態(tài)轉(zhuǎn)換為字符串形式var formatBoard func() []stringformatBoard = func() []string {var result []stringfor _, row := range board {result = append(result, strings.Join(row, ""))}return result}// 回溯函數(shù)var backTrack func(row int)backTrack = func(row int) {if row == n {res = append(res, formatBoard()) // 所有行已放置完成，記錄當(dāng)前棋盤return}for col := 0; col < n; col++ {if !isValid(row, col) {continue}board[row][col] = "Q" // 放置皇后backTrack(row + 1)    // 遞歸到下一行board[row][col] = "." // 回溯，撤銷放置}}backTrack(0) // 從第0行開始遞歸return res
}

詳細(xì)解讀：

1. 終止條件：

   • 當(dāng)所有行都放置皇后后（即row == n），將當(dāng)前棋盤狀態(tài)加入結(jié)果集。

2. 結(jié)果收集條件：

   • 在放置完所有行的皇后后，將當(dāng)前棋盤狀態(tài)board轉(zhuǎn)換為字符串格式，并存入res。

3. 去重邏輯：

   • 不存在重復(fù)，因?yàn)槊看芜f歸基于當(dāng)前棋盤狀態(tài)進(jìn)行放置，確保唯一性。

4. 遞歸控制：

   • 每行遞歸嘗試所有列的放置，通過isValid函數(shù)判斷是否沖突，遞歸完成后回溯撤銷放置。

---

13. LeetCode 37. 解數(shù)獨(dú)

題目分析：
給定一個(gè)部分填充的9x9數(shù)獨(dú)，要求填充空白位置，使得每行、每列和每個(gè)3x3子區(qū)域均包含1到9的數(shù)字。數(shù)獨(dú)謎題要求唯一解，因此需要在遞歸中保證填充的數(shù)字唯一合法。

思路解析：
通過回溯逐個(gè)填充每一個(gè)空白位置，每個(gè)位置從1到9逐一嘗試，檢查當(dāng)前數(shù)字是否符合數(shù)獨(dú)規(guī)則，若符合則遞歸填充下一個(gè)空白格。填充完成后進(jìn)行回溯，以探索其他可能解。

解數(shù)獨(dú)的回溯流程圖

Go語言實(shí)現(xiàn)：

func solveSudoku(board [][]byte) {var backTrack func() boolbackTrack = func() bool {for i := 0; i < 9; i++ {for j := 0; j < 9; j++ {// 跳過已填充的格子if board[i][j] != '.' {continue}// 嘗試填充1到9for k := '1'; k <= '9'; k++ {if isValidSudoku(board, i, j, byte(k)) {board[i][j] = byte(k) // 填充數(shù)字if backTrack() {      // 遞歸處理下一空格return true}board[i][j] = '.' // 回溯，撤銷填充}}return false // 若無合適數(shù)字則返回，回溯上層}}return true // 全部填充完成，返回true}backTrack()
}// 檢查填充是否符合數(shù)獨(dú)規(guī)則
func isValidSudoku(board [][]byte, row, col int, num byte) bool {for i := 0; i < 9; i++ {// 檢查行和列是否有相同數(shù)字if board[row][i] == num || board[i][col] == num {return false}}// 檢查3x3子區(qū)域是否有相同數(shù)字startRow, startCol := (row/3)*3, (col/3)*3for i := startRow; i < startRow+3; i++ {for j := startCol; j < startCol+3; j++ {if board[i][j] == num {return false}}}return true
}

詳細(xì)解讀：

1. 終止條件：

   • 數(shù)獨(dú)填充完所有空格時(shí)返回true，表示解數(shù)獨(dú)成功。

2. 結(jié)果收集條件：

   • 當(dāng)所有空格均填充有效數(shù)字時(shí)，返回true表示找到解。

3. 去重邏輯：

   • 每次填充數(shù)字前通過isValidSudoku檢查是否有重復(fù)，確保合法。

4. 遞歸控制：

   • 遞歸順序按行列填充，若當(dāng)前格子無合適數(shù)字，則返回上層重新選擇。

---

小結(jié)

棋盤問題的解法在回溯過程中充分利用了位置沖突檢測和條件校驗(yàn)：

1. 位置合法性檢查：每次遞歸前進(jìn)行條件校驗(yàn)，確保放置的元素（皇后或數(shù)字）符合問題規(guī)則。
2. 遞歸路徑的回溯：遞歸完成后通過回溯撤銷選擇，恢復(fù)狀態(tài)以便嘗試新的解法。
3. 多層次條件判斷：棋盤問題的遞歸邏輯中條件判斷多，尤其是涉及行、列和對角線或3x3區(qū)域的沖突檢測。

以上棋盤問題展示了如何在遞歸過程中處理復(fù)雜的棋盤狀態(tài)和規(guī)則檢測。接下來我們將繼續(xù)分析其他復(fù)雜問題的解法與實(shí)現(xiàn)。

---

八、其他復(fù)雜問

這一類問題雖然不直接涉及棋盤或固定的數(shù)組結(jié)構(gòu)，但仍可以使用回溯算法，通過遞歸探索不同的路徑組合，滿足特定的條件限制。以下分別是遞增子序列和行程重排問題的分析與實(shí)現(xiàn)。

---

14. LeetCode 491. 遞增子序列

題目分析：
給定一個(gè)整數(shù)組nums，要求找到所有長度大于等于2的遞增子序列，使得子序列中的元素按原數(shù)組中的順序排列。結(jié)果集中不能有重復(fù)的子序列。

思路解析：
遞歸生成子序列的每個(gè)元素時(shí)，確保新加入的元素滿足遞增要求，并且通過去重邏輯防止重復(fù)子序列的生成。具體來說，遞歸過程中會(huì)跳過當(dāng)前層級(jí)的重復(fù)元素，同時(shí)用一個(gè)臨時(shí)哈希表避免在同一層中選取相同的數(shù)字。

遞增子序列生成的回溯流程圖

Go語言實(shí)現(xiàn)：

func findSubsequences(nums []int) [][]int {var res [][]intvar path []intl := len(nums)var backTrack func(start int)backTrack = func(start int) {if len(path) >= 2 { // 只記錄長度大于等于2的遞增子序列temp := make([]int, len(path))copy(temp, path)res = append(res, temp)}used := make(map[int]bool) // 當(dāng)前層級(jí)去重for i := start; i < l; i++ {// 檢查遞增性及去重條件if (len(path) > 0 && nums[i] < path[len(path)-1]) || used[nums[i]] {continue}used[nums[i]] = true          // 標(biāo)記當(dāng)前元素已使用path = append(path, nums[i])  // 選擇當(dāng)前元素backTrack(i + 1)              // 遞歸到下一個(gè)位置path = path[:len(path)-1]     // 撤銷選擇，回溯}}backTrack(0)return res
}

詳細(xì)解讀：

1. 終止條件：

   • 沒有固定終止條件，每次遞歸的路徑path長度滿足>=2時(shí)將路徑加入結(jié)果集。

2. 結(jié)果收集條件：

   • 每次遞歸進(jìn)入時(shí)判斷路徑長度，若大于等于2則將路徑加入結(jié)果。

3. 去重邏輯：

   • 每一層遞歸中使用used哈希表記錄當(dāng)前層已選元素，避免重復(fù)選擇。

4. 遞增性校驗(yàn)：

   • 僅當(dāng)當(dāng)前元素大于等于路徑末尾元素時(shí)才加入路徑，確保子序列遞增。

---

15. LeetCode 332. 重新安排行程

題目分析：
給定一組行程票據(jù)，每張票據(jù)表示從某個(gè)機(jī)場出發(fā)，前往另一個(gè)機(jī)場。要求使用所有票據(jù)，按字典序返回從起點(diǎn)JFK開始的行程。

思路解析：
先對票據(jù)進(jìn)行字典序排序，然后通過回溯找到符合條件的行程路徑。遞歸過程中每次選擇一個(gè)目的地前往，若路徑完整即為解。此外，在使用票據(jù)時(shí)需要標(biāo)記票據(jù)是否被使用，確保每張票僅用一次。

重新安排行程的遞歸流程

Go語言實(shí)現(xiàn)：

import "sort"func findItinerary(tickets [][]string) []string {var res []string// 構(gòu)建鄰接表，按字典序排序每個(gè)出發(fā)地的目的地flights := make(map[string][]string)for _, ticket := range tickets {from, to := ticket[0], ticket[1]flights[from] = append(flights[from], to)}for from := range flights {sort.Strings(flights[from])}// 回溯函數(shù)var backTrack func(airport string)backTrack = func(airport string) {for len(flights[airport]) > 0 {// 每次選擇當(dāng)前機(jī)場的第一個(gè)目的地，確保字典序next := flights[airport][0]flights[airport] = flights[airport][1:] // 從鄰接表中移除已使用票backTrack(next)                         // 遞歸到下一目的地}res = append([]string{airport}, res...) // 將當(dāng)前機(jī)場插入到行程的開頭}backTrack("JFK")return res
}

詳細(xì)解讀：

1. 終止條件：

   • 在所有票據(jù)用完時(shí)終止遞歸。路徑構(gòu)建完成后將遞歸路徑res返回。

2. 結(jié)果收集條件：

   • 每次遞歸回溯時(shí)將當(dāng)前機(jī)場插入到行程路徑res開頭，形成最終的行程順序。

3. 去重邏輯：

   • 每次遞歸選擇時(shí)，使用并移除當(dāng)前目的地，避免重復(fù)使用票據(jù)。

4. 字典序控制：

   • 對每個(gè)出發(fā)地的目的地進(jìn)行字典序排序，確保按字典序優(yōu)先構(gòu)建路徑。

---

小結(jié)

在這一類復(fù)雜問題中，回溯算法需要更多的條件判斷和路徑控制來滿足題目要求：

1. 路徑的唯一性和有效性：借助條件判斷和狀態(tài)記錄，確保路徑符合題目要求。
2. 字典序或順序控制：對于順序敏感的問題，通過預(yù)排序或字典序遍歷確保路徑符合要求。
3. 遞歸回溯與去重策略：有效的去重方法可以減少重復(fù)計(jì)算，尤其是在路徑中存在重復(fù)元素時(shí)。

本章通過遞增子序列和行程安排問題展示了回溯算法在復(fù)雜條件控制中的強(qiáng)大靈活性。

總結(jié)

在本文中，我們詳細(xì)探討了回溯算法在LeetCode上多類問題的應(yīng)用?；厮菟惴ㄍㄟ^遞歸與路徑回退的組合，能夠靈活地解決多種組合、分割、子集、排列、棋盤問題以及其他復(fù)雜場景的問題。對于每一道題目，我們不僅提供了具體的解題思路，還重點(diǎn)分析了回溯算法中的關(guān)鍵概念：終止條件、路徑收集、去重邏輯和遞歸控制。

通過對每道題目的詳細(xì)解讀，本文總結(jié)出回溯算法在應(yīng)對不同題型時(shí)的共性和差異性。對于組合和子集問題，回溯算法的主要任務(wù)是控制元素的選擇順序；在排列問題中，算法必須關(guān)注排列的順序性；在棋盤問題中，遞歸條件更加復(fù)雜，需要多層次沖突檢測；而在復(fù)雜問題中，算法往往需動(dòng)態(tài)地控制路徑合法性和順序。

希望通過這篇文章，讀者能夠更加系統(tǒng)地理解回溯算法在不同問題類型中的應(yīng)用，掌握其在路徑選擇、條件判斷、狀態(tài)回退等方面的通用模式，并能夠在遇到類似問題時(shí)舉一反三，設(shè)計(jì)出高效的回溯解法。

---