Hello 算法回溯章节练习精讲全排列、子集和与 n 皇后的思考题与实现【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo回溯backtracking是《Hello 算法》中贯穿搜尋、約束滿足與組合最佳化三類問題的核心演算法。本文以繁中版回溯章節練習為骨架完整講解「知識鞏固」中的三道思考題與「程式設計練習」中的無重複元素全排列題並結合格倉庫內的全排列、子集和、n 皇后等可執行原始碼從「嘗試、回退、剪枝」的底層機制出發幫助讀者徹底理解為何回溯程式碼必須「改了什麼就恢復什麼」以及如何用剪枝消除重複解。讀完本文你將具備獨立推導與除錯回溯程式碼的能力。前置知識回溯的三個關鍵動作要理解本章練習題先回顧回溯演算法的三個基本動作詳見回溯演算法一文嘗試attempt做出一個選擇更新當前狀態回退backtracking撤銷上一步的選擇恢復到之前的狀態剪枝pruning根據約束條件提前跳過不可能產生解的搜尋分支。一個通用的回溯框架如下Python 偽碼形式摘自回溯演算法的框架程式碼def backtrack(state, choices, res): 回溯演算法框架 if is_solution(state): # 判斷是否為解 record_solution(state, res) return for choice in choices: # 走訪所有選擇 if is_valid(state, choice): # 剪枝判斷選擇是否合法 make_choice(state, choice) # 嘗試做出選擇更新狀態 backtrack(state, choices, res) undo_choice(state, choice) # 回退撤銷選擇恢復狀態練習題的核心就是反覆檢驗「嘗試時改動了哪些狀態回退時是否完整恢復」。知識鞏固一這段排列演算法會漏掉結果嗎題目回顧一個回溯演算法按1、2、3的順序嘗試生成全部排列。每次選擇數字x時它會把x加到當前路徑末尾把x標記為「已使用」遞迴填寫下一個位置。遞迴返回後同學只從路徑末尾刪除了x然後繼續嘗試下一個數字。問題 1演算法首先得到哪個排列它還能得到全部 6 個排列嗎問題 2遞迴返回上一層前只刪除路徑末尾的數字是否足夠如果不夠還需要做什麼說明理由。參考答案與解析問題 1它首先得到[1, 2, 3]但無法得到全部排列。雖然返回時路徑變短了數字 1、2、3 的標記仍都是「已使用」後續分支便沒有可選數字。問題 2不夠。刪除路徑末尾的x後還必須把x重新標記為「未使用」。當前路徑和已使用標記共同描述搜尋狀態選擇時修改了兩處回退時也必須把兩處都恢復其他分支才能再次選擇x。結合原始碼印證狀態是「路徑 標記」的整體這一題的關鍵教訓在於回溯的狀態不是只有路徑還包括輔助標記。請看倉庫中permutations_i.py的正確實現def backtrack(state, choices, selected, res): # 當狀態長度等於元素數量時記錄解 if len(state) len(choices): res.append(list(state)) return for i, choice in enumerate(choices): # 剪枝不允許重複選擇元素 if not selected[i]: # 嘗試做出選擇更新狀態 selected[i] True state.append(choice) backtrack(state, choices, selected, res) # 回退撤銷選擇恢復到之前的狀態 selected[i] False state.pop()對照上面的錯誤版本正確程式碼在回退時同時執行selected[i] False恢復標記與state.pop()刪除路徑末尾兩者缺一不可。若只保留state.pop()則第一輪選完1後selected[0]永遠保持True第二輪、第三輪都無法再選1搜尋提前「卡死」這正是練習題描述的「漏掉結果」現象。布林陣列selected的長度與choices相同selected[i]表示choices[i]是否已選入當前排列剪枝條件not selected[i]保證每個元素在每個排列中恰好出現一次遞迴終止條件len(state) len(choices)對應「路徑長度達到 n 時記錄解」。Java 版本可見permutations_i.java結構與 Python 版一一對應state.add(choice)與state.remove(state.size() - 1)成對出現selected[i] true與selected[i] false成對出現印證了「改什麼就恢復什麼」的對稱性原則。知識鞏固二數字的選擇順序重要嗎題目回顧給定排好序的陣列[2, 3, 5]和目標值 5每個數可以重複選擇。演算法規定每條搜尋路徑中的數字只能按從小到大的順序出現。問題 1能得到哪些不同的組合問題 2為什麼同一組數字不需要按不同順序重複搜尋「從小到大」的限制起到了什麼作用問題 3當前路徑為[3]、還差 2 時下一個候選數是 3。為什麼此時可以停止檢查這一層後面的所有候選數參考答案與解析問題 1不同的組合為[2, 3]和[5]。問題 2本題把[2, 3]和[3, 2]看作同一種組合數字的選擇順序不計入答案。規定路徑中的數字從小到大出現就能在搜尋時直接跳過[3, 2]這類重複組合。問題 3當前還差 2而候選數 3 已經大於 2。因為陣列已經排好序3 後面的候選數只會更大也都不可能加入當前組合所以可以直接結束這一層的檢查。結合原始碼印證start參數與越界剪枝這一題對應subset_sum_i.py的實現。先看核心程式碼def backtrack(state, target, choices, start, res): # 子集和等於 target 時記錄解 if target 0: res.append(list(state)) return # 剪枝二從 start 開始遍歷避免生成重複子集 for i in range(start, len(choices)): # 剪枝一若子集和超過 target則直接結束迴圈 # 這是因為陣列已排序後邊元素更大子集和一定超過 target if target - choices[i] 0: break state.append(choices[i]) backtrack(state, target - choices[i], choices, i, res) state.pop()三處設計正好對應練習題的三個答案start參數實現「從小到大」做出選擇choices[i]後下一輪從索引i而非0開始走訪。這使得選擇序列滿足i1 ≤ i2 ≤ … ≤ im從根本上排除了[3, 2]這類逆序重複組合——這就是問題 2 中「限制數字順序」的程式碼層面實現。注意因為元素可重複選取下一輪仍從i開始而不是i1這與subset_sum_ii.py中「每個元素只選一次、下一輪從i1開始」形成對比。排序 提前break實現「越界剪枝」入口處先執行nums.sort()排序迴圈內一旦target - choices[i] 0即加入該元素後總和超過目標由於後續元素更大直接break結束整層迴圈。這正是問題 3 的答案還差 2 時遇到候選數 3可以直接停止檢查後面的所有候選數因為它們只會更大。在target上做減法省去額外的total累加變數target 0時即記錄解程式碼更簡潔。以輸入[3, 4, 5]、target 9執行檔案內Driver Code即此用例輸出[3, 3, 3]與[4, 5]與練習題[2, 3, 5]/target5給出的[2, 3]、[5]屬同一套機制。知識鞏固三下一枚皇后可以放在哪些位置題目回顧在一個4 × 4棋盤上按行放置皇后行、列下標都從 0 開始。目前已經在(0, 1)和(1, 3)放置了皇后現在要在第 2 行放置下一個皇后。問題 1哪些列會因為「同列」而被排除問題 2在剩餘列中哪些位置會因為「同一條對角線」而被排除問題 3第 2 行還剩哪些位置可以嘗試參考答案與解析問題 1第 1 列和第 3 列已經有皇后因此位置(2, 1)和(2, 3)被排除。問題 2在剩餘位置中(2, 2)與(1, 3)位於同一條對角線上因此也被排除。位置(2, 0)與已有兩個皇后都不在同列或同一條對角線上。問題 3第 2 行可以嘗試的位置只有(2, 0)。這一步只說明當前放置合法之後若無法完成棋盤仍需回退並嘗試更早的其他選擇。結合原始碼印證列與對角線的三重剪枝這一題對應n_queens.py。先看回溯主體def backtrack(row, n, state, res, cols, diags1, diags2): # 當放置完所有行時記錄解 if row n: res.append([list(row) for row in state]) return for col in range(n): diag1 row - col n - 1 diag2 row col # 剪枝不允許該格子所在列、主對角線、次對角線上存在皇后 if not cols[col] and not diags1[diag1] and not diags2[diag2]: state[row][col] Q cols[col] diags1[diag1] diags2[diag2] True backtrack(row 1, n, state, res, cols, diags1, diags2) state[row][col] # cols[col] diags1[diag1] diags2[diag2] False逐項對照練習題同列排除問題 1cols[col]為布林陣列長度n。第 1、3 列已有皇后故cols[1] cols[3] True(2, 1)、(2, 3)被剪枝。主對角線排除問題 2 的一部分主對角線\上所有格子的row - col恆定程式碼用diag1 row - col n - 1將負索引平移到非負範圍row - col的範圍是[-n1, n-1]加上n-1後對應長度2n-1的陣列diags1。次對角線排除問題 2 的另一部分次對角線/上所有格子的row col恆定範圍[0, 2n-2]對應長度2n-1的陣列diags2。驗證練習題的具體座標皇后在(0, 1)與(1, 3)則cols[1]、cols[3]為True格子(2, 2)的row - col 0與(1, 3)的row - col -2不同但需要檢查次對角線row col(2, 2)的row col 4(1, 3)的row col 4兩者相等故(2, 2)與(1, 3)位於同一條次對角線上被diags2剪枝。最終只剩(2, 0)可嘗試——與練習題答案完全一致。此外n_queens.py採用逐行放置策略皇后數與行數同為n每行恰好放一個皇后這本身就剪掉了「同一行出現多個皇后」的所有分支。檔案內Driver Code以n 4執行輸出 2 種方案可自行執行驗證python codes/python/chapter_backtracking/n_queens.py程式設計練習無重複元素的全排列題目要求整數陣列nums至少包含一個元素並且其中各元素互不相同。請列出把這些元素各使用一次所能形成的全部順序並將每一種順序作為一個陣列返回。結果中各排列的先後次序不作要求。請使用回溯並用布林陣列記錄每個位置的元素是否已經選入當前排列。解題提示遞迴深度表示正在填寫排列中的第幾個位置每一層只嘗試尚未使用的元素路徑長度達到nums的長度時把它的副本加入答案。完整參考實現基於以上提示結合倉庫中permutations_i.py的完整實現逐行對照提示def backtrack(state, choices, selected, res): 回溯演算法全排列 I # 提示 3路徑長度達到 nums 的長度時記錄解 if len(state) len(choices): res.append(list(state)) # 注意必須複製副本不能直接加入 state return # 遍歷所有選擇 for i, choice in enumerate(choices): # 提示 2每一層只嘗試尚未使用的元素 if not selected[i]: # 嘗試做出選擇更新狀態 selected[i] True state.append(choice) # 提示 1遞迴深度即正在填寫的位置 backtrack(state, choices, selected, res) # 回退撤銷選擇恢復到之前的狀態 selected[i] False state.pop() def permutations_i(nums): 全排列 I res [] backtrack(state[], choicesnums, selected[False] * len(nums), resres) return res實現細節與易錯點記錄解時必須複製副本res.append(list(state))複製當前路徑。若直接res.append(state)後續回退時的state.pop()會同時改動已記錄的解——這是回溯程式碼中最經典的隱蔽 Bug。「遞迴深度 位置」每次遞迴調用對應填寫下一個位置因此不需要額外的depth參數直接用len(state)判斷是否填滿。布林陣列與交換法的對比LeetCode 46 題的常見題解透過交換陣列元素把已選元素依次放到陣列前部本練習則使用布林陣列selected記錄每個位置是否已選。兩種方法都能避免同一元素被重複選擇但程式碼結構不同交換法原地修改nums、無需額外標記陣列布林陣列法狀態更直觀、適合與練習一中的「狀態恢復」分析對照。執行驗證以nums [1, 2, 3]執行permutations_i.py 的 Driver Code 即此用例輸出全部 6 個排列python codes/python/chapter_backtracking/permutations_i.py # 輸入數組 nums [1, 2, 3] # 所有排列 res [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]延伸思考從練習題到進階剪枝本章練習的三道思考題本質上是在檢驗回溯的兩大主題——狀態恢復與剪枝去重練習一考的是「狀態恢復不完整」的後果selected標記未恢復導致漏解練習二考的是「順序約束剪枝」start參數 排序 提前break既去重又提速練習三考的是「多重約束剪枝」cols、diags1、diags2三組標記聯合判斷。在此基礎上可以繼續探究倉庫中的進階版本含重複元素的全排列permutations_ii.py每輪維護一個duplicated雜湊集合保證相等元素在本輪只被選擇一次配合selected實現「相等元素剪枝」含重複元素的子集和subset_sum_ii.py四重剪枝——start去重子集、target - choices[i] 0提前結束、i start and choices[i] choices[i-1]跳過相等元素、i 1保證每個元素只用一次完整理論背景回溯的「嘗試—回退—剪枝」框架、常用術語解、約束條件、狀態、嘗試、回退、剪枝以及時間/空間複雜度分析見回溯演算法三類典型問題的完整講解見全排列問題、子集和問題與n 皇后問題。建議讀者按照「先獨立作答練習題 → 對照參考答案 → 對照倉庫原始碼逐行驗證 → 手寫一遍程式碼」的順序完成本章這四步正是把回溯從「看得懂」變成「寫得出」的最短路徑。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
Hello 算法回溯章节练习精讲：全排列、子集和与 n 皇后的思考题与实现
Hello 算法回溯章节练习精讲全排列、子集和与 n 皇后的思考题与实现【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo回溯backtracking是《Hello 算法》中贯穿搜尋、約束滿足與組合最佳化三類問題的核心演算法。本文以繁中版回溯章節練習為骨架完整講解「知識鞏固」中的三道思考題與「程式設計練習」中的無重複元素全排列題並結合格倉庫內的全排列、子集和、n 皇后等可執行原始碼從「嘗試、回退、剪枝」的底層機制出發幫助讀者徹底理解為何回溯程式碼必須「改了什麼就恢復什麼」以及如何用剪枝消除重複解。讀完本文你將具備獨立推導與除錯回溯程式碼的能力。前置知識回溯的三個關鍵動作要理解本章練習題先回顧回溯演算法的三個基本動作詳見回溯演算法一文嘗試attempt做出一個選擇更新當前狀態回退backtracking撤銷上一步的選擇恢復到之前的狀態剪枝pruning根據約束條件提前跳過不可能產生解的搜尋分支。一個通用的回溯框架如下Python 偽碼形式摘自回溯演算法的框架程式碼def backtrack(state, choices, res): 回溯演算法框架 if is_solution(state): # 判斷是否為解 record_solution(state, res) return for choice in choices: # 走訪所有選擇 if is_valid(state, choice): # 剪枝判斷選擇是否合法 make_choice(state, choice) # 嘗試做出選擇更新狀態 backtrack(state, choices, res) undo_choice(state, choice) # 回退撤銷選擇恢復狀態練習題的核心就是反覆檢驗「嘗試時改動了哪些狀態回退時是否完整恢復」。知識鞏固一這段排列演算法會漏掉結果嗎題目回顧一個回溯演算法按1、2、3的順序嘗試生成全部排列。每次選擇數字x時它會把x加到當前路徑末尾把x標記為「已使用」遞迴填寫下一個位置。遞迴返回後同學只從路徑末尾刪除了x然後繼續嘗試下一個數字。問題 1演算法首先得到哪個排列它還能得到全部 6 個排列嗎問題 2遞迴返回上一層前只刪除路徑末尾的數字是否足夠如果不夠還需要做什麼說明理由。參考答案與解析問題 1它首先得到[1, 2, 3]但無法得到全部排列。雖然返回時路徑變短了數字 1、2、3 的標記仍都是「已使用」後續分支便沒有可選數字。問題 2不夠。刪除路徑末尾的x後還必須把x重新標記為「未使用」。當前路徑和已使用標記共同描述搜尋狀態選擇時修改了兩處回退時也必須把兩處都恢復其他分支才能再次選擇x。結合原始碼印證狀態是「路徑 標記」的整體這一題的關鍵教訓在於回溯的狀態不是只有路徑還包括輔助標記。請看倉庫中permutations_i.py的正確實現def backtrack(state, choices, selected, res): # 當狀態長度等於元素數量時記錄解 if len(state) len(choices): res.append(list(state)) return for i, choice in enumerate(choices): # 剪枝不允許重複選擇元素 if not selected[i]: # 嘗試做出選擇更新狀態 selected[i] True state.append(choice) backtrack(state, choices, selected, res) # 回退撤銷選擇恢復到之前的狀態 selected[i] False state.pop()對照上面的錯誤版本正確程式碼在回退時同時執行selected[i] False恢復標記與state.pop()刪除路徑末尾兩者缺一不可。若只保留state.pop()則第一輪選完1後selected[0]永遠保持True第二輪、第三輪都無法再選1搜尋提前「卡死」這正是練習題描述的「漏掉結果」現象。布林陣列selected的長度與choices相同selected[i]表示choices[i]是否已選入當前排列剪枝條件not selected[i]保證每個元素在每個排列中恰好出現一次遞迴終止條件len(state) len(choices)對應「路徑長度達到 n 時記錄解」。Java 版本可見permutations_i.java結構與 Python 版一一對應state.add(choice)與state.remove(state.size() - 1)成對出現selected[i] true與selected[i] false成對出現印證了「改什麼就恢復什麼」的對稱性原則。知識鞏固二數字的選擇順序重要嗎題目回顧給定排好序的陣列[2, 3, 5]和目標值 5每個數可以重複選擇。演算法規定每條搜尋路徑中的數字只能按從小到大的順序出現。問題 1能得到哪些不同的組合問題 2為什麼同一組數字不需要按不同順序重複搜尋「從小到大」的限制起到了什麼作用問題 3當前路徑為[3]、還差 2 時下一個候選數是 3。為什麼此時可以停止檢查這一層後面的所有候選數參考答案與解析問題 1不同的組合為[2, 3]和[5]。問題 2本題把[2, 3]和[3, 2]看作同一種組合數字的選擇順序不計入答案。規定路徑中的數字從小到大出現就能在搜尋時直接跳過[3, 2]這類重複組合。問題 3當前還差 2而候選數 3 已經大於 2。因為陣列已經排好序3 後面的候選數只會更大也都不可能加入當前組合所以可以直接結束這一層的檢查。結合原始碼印證start參數與越界剪枝這一題對應subset_sum_i.py的實現。先看核心程式碼def backtrack(state, target, choices, start, res): # 子集和等於 target 時記錄解 if target 0: res.append(list(state)) return # 剪枝二從 start 開始遍歷避免生成重複子集 for i in range(start, len(choices)): # 剪枝一若子集和超過 target則直接結束迴圈 # 這是因為陣列已排序後邊元素更大子集和一定超過 target if target - choices[i] 0: break state.append(choices[i]) backtrack(state, target - choices[i], choices, i, res) state.pop()三處設計正好對應練習題的三個答案start參數實現「從小到大」做出選擇choices[i]後下一輪從索引i而非0開始走訪。這使得選擇序列滿足i1 ≤ i2 ≤ … ≤ im從根本上排除了[3, 2]這類逆序重複組合——這就是問題 2 中「限制數字順序」的程式碼層面實現。注意因為元素可重複選取下一輪仍從i開始而不是i1這與subset_sum_ii.py中「每個元素只選一次、下一輪從i1開始」形成對比。排序 提前break實現「越界剪枝」入口處先執行nums.sort()排序迴圈內一旦target - choices[i] 0即加入該元素後總和超過目標由於後續元素更大直接break結束整層迴圈。這正是問題 3 的答案還差 2 時遇到候選數 3可以直接停止檢查後面的所有候選數因為它們只會更大。在target上做減法省去額外的total累加變數target 0時即記錄解程式碼更簡潔。以輸入[3, 4, 5]、target 9執行檔案內Driver Code即此用例輸出[3, 3, 3]與[4, 5]與練習題[2, 3, 5]/target5給出的[2, 3]、[5]屬同一套機制。知識鞏固三下一枚皇后可以放在哪些位置題目回顧在一個4 × 4棋盤上按行放置皇后行、列下標都從 0 開始。目前已經在(0, 1)和(1, 3)放置了皇后現在要在第 2 行放置下一個皇后。問題 1哪些列會因為「同列」而被排除問題 2在剩餘列中哪些位置會因為「同一條對角線」而被排除問題 3第 2 行還剩哪些位置可以嘗試參考答案與解析問題 1第 1 列和第 3 列已經有皇后因此位置(2, 1)和(2, 3)被排除。問題 2在剩餘位置中(2, 2)與(1, 3)位於同一條對角線上因此也被排除。位置(2, 0)與已有兩個皇后都不在同列或同一條對角線上。問題 3第 2 行可以嘗試的位置只有(2, 0)。這一步只說明當前放置合法之後若無法完成棋盤仍需回退並嘗試更早的其他選擇。結合原始碼印證列與對角線的三重剪枝這一題對應n_queens.py。先看回溯主體def backtrack(row, n, state, res, cols, diags1, diags2): # 當放置完所有行時記錄解 if row n: res.append([list(row) for row in state]) return for col in range(n): diag1 row - col n - 1 diag2 row col # 剪枝不允許該格子所在列、主對角線、次對角線上存在皇后 if not cols[col] and not diags1[diag1] and not diags2[diag2]: state[row][col] Q cols[col] diags1[diag1] diags2[diag2] True backtrack(row 1, n, state, res, cols, diags1, diags2) state[row][col] # cols[col] diags1[diag1] diags2[diag2] False逐項對照練習題同列排除問題 1cols[col]為布林陣列長度n。第 1、3 列已有皇后故cols[1] cols[3] True(2, 1)、(2, 3)被剪枝。主對角線排除問題 2 的一部分主對角線\上所有格子的row - col恆定程式碼用diag1 row - col n - 1將負索引平移到非負範圍row - col的範圍是[-n1, n-1]加上n-1後對應長度2n-1的陣列diags1。次對角線排除問題 2 的另一部分次對角線/上所有格子的row col恆定範圍[0, 2n-2]對應長度2n-1的陣列diags2。驗證練習題的具體座標皇后在(0, 1)與(1, 3)則cols[1]、cols[3]為True格子(2, 2)的row - col 0與(1, 3)的row - col -2不同但需要檢查次對角線row col(2, 2)的row col 4(1, 3)的row col 4兩者相等故(2, 2)與(1, 3)位於同一條次對角線上被diags2剪枝。最終只剩(2, 0)可嘗試——與練習題答案完全一致。此外n_queens.py採用逐行放置策略皇后數與行數同為n每行恰好放一個皇后這本身就剪掉了「同一行出現多個皇后」的所有分支。檔案內Driver Code以n 4執行輸出 2 種方案可自行執行驗證python codes/python/chapter_backtracking/n_queens.py程式設計練習無重複元素的全排列題目要求整數陣列nums至少包含一個元素並且其中各元素互不相同。請列出把這些元素各使用一次所能形成的全部順序並將每一種順序作為一個陣列返回。結果中各排列的先後次序不作要求。請使用回溯並用布林陣列記錄每個位置的元素是否已經選入當前排列。解題提示遞迴深度表示正在填寫排列中的第幾個位置每一層只嘗試尚未使用的元素路徑長度達到nums的長度時把它的副本加入答案。完整參考實現基於以上提示結合倉庫中permutations_i.py的完整實現逐行對照提示def backtrack(state, choices, selected, res): 回溯演算法全排列 I # 提示 3路徑長度達到 nums 的長度時記錄解 if len(state) len(choices): res.append(list(state)) # 注意必須複製副本不能直接加入 state return # 遍歷所有選擇 for i, choice in enumerate(choices): # 提示 2每一層只嘗試尚未使用的元素 if not selected[i]: # 嘗試做出選擇更新狀態 selected[i] True state.append(choice) # 提示 1遞迴深度即正在填寫的位置 backtrack(state, choices, selected, res) # 回退撤銷選擇恢復到之前的狀態 selected[i] False state.pop() def permutations_i(nums): 全排列 I res [] backtrack(state[], choicesnums, selected[False] * len(nums), resres) return res實現細節與易錯點記錄解時必須複製副本res.append(list(state))複製當前路徑。若直接res.append(state)後續回退時的state.pop()會同時改動已記錄的解——這是回溯程式碼中最經典的隱蔽 Bug。「遞迴深度 位置」每次遞迴調用對應填寫下一個位置因此不需要額外的depth參數直接用len(state)判斷是否填滿。布林陣列與交換法的對比LeetCode 46 題的常見題解透過交換陣列元素把已選元素依次放到陣列前部本練習則使用布林陣列selected記錄每個位置是否已選。兩種方法都能避免同一元素被重複選擇但程式碼結構不同交換法原地修改nums、無需額外標記陣列布林陣列法狀態更直觀、適合與練習一中的「狀態恢復」分析對照。執行驗證以nums [1, 2, 3]執行permutations_i.py 的 Driver Code 即此用例輸出全部 6 個排列python codes/python/chapter_backtracking/permutations_i.py # 輸入數組 nums [1, 2, 3] # 所有排列 res [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]延伸思考從練習題到進階剪枝本章練習的三道思考題本質上是在檢驗回溯的兩大主題——狀態恢復與剪枝去重練習一考的是「狀態恢復不完整」的後果selected標記未恢復導致漏解練習二考的是「順序約束剪枝」start參數 排序 提前break既去重又提速練習三考的是「多重約束剪枝」cols、diags1、diags2三組標記聯合判斷。在此基礎上可以繼續探究倉庫中的進階版本含重複元素的全排列permutations_ii.py每輪維護一個duplicated雜湊集合保證相等元素在本輪只被選擇一次配合selected實現「相等元素剪枝」含重複元素的子集和subset_sum_ii.py四重剪枝——start去重子集、target - choices[i] 0提前結束、i start and choices[i] choices[i-1]跳過相等元素、i 1保證每個元素只用一次完整理論背景回溯的「嘗試—回退—剪枝」框架、常用術語解、約束條件、狀態、嘗試、回退、剪枝以及時間/空間複雜度分析見回溯演算法三類典型問題的完整講解見全排列問題、子集和問題與n 皇后問題。建議讀者按照「先獨立作答練習題 → 對照參考答案 → 對照倉庫原始碼逐行驗證 → 手寫一遍程式碼」的順序完成本章這四步正是把回溯從「看得懂」變成「寫得出」的最短路徑。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
