[LeetCode 核心演算法] 回溯法（Backtracking）：最精簡解題技巧與必練題目

回溯法是「暴力搜尋法」（窮舉搜尋、枚舉法）中一種，又名 Backtracking。

用試錯的思想，在分步驟解決問題的過程中，

這種演算法（algorithm）是當探索到某一步時，

發現原先選擇，並不能得到有效的正確的解答的時候，

就「退回」一步，甚至是上幾步的計算，重新選擇。

也可以說回溯法（Backtracking），是優化後的「枚舉法」。

為解答加上一個「約束條件」，

若是遇到不符合條件的，則不從這個方向繼續枚舉，

退回上一步嘗試別的路徑。

一、回溯法（Backtracking）的核心概念

回溯法（Backtracking）可以分為兩個概念

1. 枚舉 enumerate：每一步列出所有可能的下一步一一測試。
2. 剪枝 pruning：遇到不符合條件的下一步便省略，不再繼續枚舉。

二、回溯法（Backtracking）的應用範例

1. 全排列（Permutations）問題

1. 問題：用程式列出所有由 1、2、3 構成的不重複序列。
2. 約束條件（不重複）：過濾重複的組合。
3. 解法：用回溯法來解決這個問題。我們逐步生成排列，每次選一個未用過的數字加入，直到排列長度達到 3。若某數字已在排列中，就跳過。完成排列後，將其加入結果中，重複這個過程直到列出所有可能。

const res = [];

for (let i = 1; i <= 3; i +=1) {
  for (let j = 1; j <= 3; j +=1) {
    if (i === ｊ) {continue}
    for (let k = 1; k <= 3; k +=1) {
      if (i === k || ｉ === k) {continue}
      res.push([i, j, k])
    }
  }
}
/* 
[ [ 1, 2, 3 ], 
   [ 1, 3, 2 ], 
   [ 2, 1, 3 ], 
   [ 2, 3, 1 ], 
   [ 3, 1, 2 ], 
   [ 3, 2, 1 ] ] 
*/

2 . 子集問題（Subsets）

1. 問題： 給定一個不含重複數字的整數集合，找出所有可能的子集。
2. 解法： 回溯法在這個問題中非常適合，因為它可以逐步構建子集，並且在每一步都可以選擇是否包含某個元素。通過遞歸地構建子集，最終可以生成所有可能的組合。

function subsets(nums) {
  const res = [];
  
  function backtrack(start, path) {
    res.push([...path]);
    
    for (let i = start; i < nums.length; i += 1) {
      path.push(nums[i]);
      backtrack(i + 1, path);
      path.pop();
    }
  }
  
  backtrack(0, []);
  return res;
}

/*
輸入: [1,2,3]
輸出: 
[
  [], [1], [2], [3],
  [1,2], [1,3], [2,3],
  [1,2,3]
]

3. 組合問題（Combinations）

1. 問題： 從 1 到 n 的整數中，選擇 k 個數字，找出所有可能的組合。
2. 解法： 與子集問題類似，組合問題也是回溯法的典型應用場景。這裡需要在每一步驟中選擇一個數字並繼續進行遞歸，直到選出 k 個數字。

function combine(n, k) {
  const res = [];
  
  function backtrack(start, path) {
    if (path.length === k) {
      res.push([...path]);
      return;
    }
    
    for (let i = start; i <= n; i += 1) {
      path.push(i);
      backtrack(i + 1, path);
      path.pop();
    }
  }
  
  backtrack(1, []);
  return res;
}

/*
輸入: n = 4, k = 2
輸出: 
[
  [2,4], [3,4], [2,3], [1,2],
  [1,3], [1,4]
]

4. 字符串分割問題（Palindrome Partitioning）

1. 問題： 將一個字符串分割為回文子串，使得每個子串都是回文，並列出所有可能的分割方式。（回文就是一個字符串，無論從前往後讀還是從後往前讀，都是一樣的。）
2. 約束條件： 每個分割出的子串都必須是回文。
3. 解法： 在每一步驟中，嘗試從當前位置開始找到一個回文子串，然後對剩下的部分進行遞歸處理。

function partition(s) {
  const res = [];
  
  function isPalindrome(str) {
    let left = 0, right = str.length - 1;
    while (left < right) {
      if (str[left] !== str[right]) return false;
      left += 1;
      right -= 1;
    }
    return true;
  }
  
  function backtrack(start, path) {
    if (start === s.length) {
      res.push([...path]);
      return;
    }
    
    for (let i = start; i < s.length; i += 1) {
      const subStr = s.substring(start, i + 1);
      if (isPalindrome(subStr)) {
        path.push(subStr);
        backtrack(i + 1, path);
        path.pop();
      }
    }
  }
  
  backtrack(0, []);
  return res;
}

/*
輸入: "aab"
輸出: 
[
  ["aa","b"], 
  ["a","a","b"]
]

三、常見的回溯法（Backtracking）問題

1. 46. Permutations： 找出所有數字序列的全排列。
2. 51. N-Queens： 解決 N 皇后問題，在 N×N 的棋盤上，擺放 N 個皇后，使得每個皇后都不能相互攻擊。
3. 688. Knight Probability in Chessboard：計算騎士在國際象棋棋盤上的某一位置上移動的概率。

四、回溯法（Backtracking）的優點與缺點

優點

• 回溯法是一種通用且強大的解決問題的方法，特別適合解決需要搜索所有可能解的問題。
• 通過剪枝技術，回溯法可以在實際應用中大大提高效率。

缺點

• 回溯法的計算量可能非常龐大，特別是當問題的搜索空間很大時，可能會導致時間複雜度急劇增加，從而難以在實際應用中處理。
• 需要仔細設計剪枝策略，以避免無效的路徑佔用過多資源。

五、回溯法（Backtracking）是強大的演算法

回溯法作為一種強大的搜索演算法（algorithm），在解決諸如排列、組合、子集和回文分割等問題時表現出色。

儘管在面對大規模問題時可能會遇到效率問題，但通過合理的剪枝策略和優化技術，回溯法依然是許多複雜問題的有效解決方案。

參考資料
1. JavaScript 學演算法（二十五）- 回溯法
2. Day27:Backtracking -回溯法
3. 簡單易懂的回溯演算法（Back Tracking)
4. 超圖解！一次搞懂演算法｜入門篇（Python）