Backtracking

tags: Algorithm

Notes:

  1. 暴力搜索法通常由巢狀迴圈組成,而巢狀迴圈在擁有相同子架構下,定義約束條件 (離開迴圈的條件),可以將巢狀迴圈改成單一迴圈加上遞迴
  2. 而backtracking只是暴力搜索法加上條件,來避免不必要的搜索而已 (回溯框架=條件剪枝+遞迴窮舉)
  3. 隨時避免枚舉不正確的數值。一旦發現不正確的數值,就不遞迴至下一層,而是回溯至上一層,節省時間。
  4. 若給的資料有重複元素,在backtracking可能出現重複的狀況,故使用回溯框架外,還需要使用額外的判斷式去檢查
  5. 有時候剪枝需要先進行排序

Tutorial:

  1. https://web.ntnu.edu.tw/~algo/Backtracking.html
  2. https://haogroot.com/2020/09/21/backtracking-leetcode/

https://www.youtube.com/watch?v=nrHTtjkYEyQ