演算法 · 5 個細項
Recursion & Backtracking遞迴與回溯
回溯是有紀律的窮舉:每一步做一個選擇、往下遞迴、回來時撤銷選擇。它是 DFS 在「決策樹」上的版本,解數獨、排列組合、N 皇后都靠它,剪枝則決定跑得快不快。
為什麼要學 Recursion & Backtracking
現實中的應用細項
5 篇#演算法複雜度難度狀態
01Subsets 子集每個元素選或不選,2ⁿ 種用在:功能開關組合測試、冪集列舉O(2ⁿ·n)空間 O(n)可學習02Permutations 排列用 used 陣列或交換法用在:排程順序、路徑列舉O(n!·n)空間 O(n)可學習03Combinations & Combination Sum 組合與剪枝從 start 開始避免重複,排序後提前剪枝用在:湊金額、選隊員指數空間 O(n)可學習04N-Queens N 皇后逐列放置,用集合記錄被攻擊的欄與對角線用在:約束滿足問題的原型:排課、排班指數空間 O(n)可學習05Word Search 網格回溯在網格上 DFS 並回復標記用在:文字遊戲、迷宮路徑列舉O(m·n·4ᴸ)空間 O(L)可學習