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

• Exercises:
  https://leetcode.com/problems/combination-sum/discuss/16502/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning)