Brute-Force 暴力法/窮舉法｜Backtracking 回溯法

Brute-Force（暴力法 / 窮舉法）

列出所有可能的解答候選，再保留那些通過驗證的解答候選

例題

• Leetcode # 17. Letter Combinations of a Phone Number
• Leetcode # 46. Permutations
• Leetcode # 77. Combinations
• Leetcode # 97. Interleaving String
• Leetcode # 2850. Minimum Moves to Spread Stones Over Grid

Backtracking（回溯法）

Brute-Force 的一種

1. 嘗試分步的解決問題
2. 當現在這一步不符合條件時 ⇒ 退回上一步

經常使用遞迴 (recursion) 來實現 backtracking

Difference with Dynamic Programing

backtracking 和 top-down 的 dynamic programing 都：

• 把母問題拆解成子問題：
  從最後的狀態（母問題）開始
  每次讀取其最後一步決策並回到決策前的狀態
  直到回到初始狀態即可獲得最佳決策
• 使用 recursion 來實現

backtracking 注重的是窮舉
dynamic programing 則是注重於 overlapping subproblems

dynamic programing 只需要輸出最佳結果
而 backtracking 需要連同過程一起輸出

可以用 backtracking 解決的問題
亦能用 bottom-up 的 dynamic programing 實現
並且進一步減少記憶體空間的消耗

有時可用 BFS 或 DFS 來實現

• Leetcode # 97. Interleaving String

複製物件

Python

list: lst_b = lst_a[:]

node: 使用 recursive function

例題

• Leetcode # 17. Letter Combinations of a Phone Number
• Leetcode # 46. Permutations
• Leetcode # 77. Combinations
• Leetcode # 97. Interleaving String
• Leetcode # 2850. Minimum Moves to Spread Stones Over Grid

排列

• Leetcode # 46. Permutations

組合

• Leetcode # 17. Letter Combinations of a Phone Number
• Leetcode # 77. Combinations
• Leetcode # 894. All Possible Full Binary Trees

Last Updated on 2023/08/25 by A1go