Leetcode 邁向千題的關卡,想要把所有題目刷過一遍,對於一位上班族來說就跟寫出來的程式沒有 bug 一樣困難,因此想要將刷題常用的觀念技巧與其對應題目整理出來,一方面可以整理自己思緒,也可以做為未來複習用。
這系列文章會一直持續下去,算是作為工程師職涯的隨身裝備。
何謂回溯法
回溯法的處理方式就像窮舉法,將所有可能的路徑都窮舉出來,接著每條岔路都派人走下去,換個角度來看,其實這個過程就如同在決策樹或是多子樹上遍歷 (Tree Traversal) 。
但如果把每條路都確實走過,這樣的作法的時間複雜度相當高,所以回溯法有時可以使用剪枝 (pruning) 的技巧提高效率,不用將所有解法都窮舉出來。
回溯法大部份用來解決廣義的搜索問題,從許多可能的解中找出滿足要求的所有解,回溯法可以應用於以下類型:
- 八皇后問題
- DFS : DFS 也是 Backtracking 的一種型態,但 DFS 更強調搜尋的順序是以深度優先。
- 排列組合
- 0-1 背包問題