回溯法是一種系統性地搜尋所有可能解的演算法。透過「選擇、探索、撤銷」三步驟,在搜尋樹上進行深度優先搜尋。
Notes:
- 回溯的核心模板:做選擇 → 遞迴 → 撤銷選擇
- 剪枝 (Pruning) 是提升效率的關鍵
- 排列 vs 組合 vs 子集,三種變體的差異要掌握
跨倉庫導讀#
#17
Letter Combinations of a Phone Number
#39
Combination Sum
#40
Combination Sum II
#46
Permutations
#47
Permutations II
#51
N-Queens
#52
N Queens II
#77
Combinations
#78
Subsets
#79
Word Search
#90
Subsets II
#93
Restore IP Addresses
#131
Palindrome Partitioning
#473
Matchsticks to Square
#698
Partition to K Equal Sum Subsets
#1239
Maximum Length of a Concatenated String With Unique Characters
#1849
Splitting a String Into Descending Consecutive Values
#1980
Find Unique Binary String