回溯算法（Backtracking）详解

回溯算法是一种通过探索所有可能的候选解来找出所有（或部分）解的算法。它常用于解决组合问题、排列问题、子集问题、棋盘问题等。

核心思想

回溯 = 递归 + 剪枝。其基本思路是：

• 从一个初始状态开始，尝试每一种可能的选择；
• 如果当前选择不能得到合法解，则“回退”到上一步（即回溯）；
• 重复上述过程，直到找到所有可行解或穷尽所有可能性。

典型应用场景

• N 皇后问题
• 全排列（Permutations）
• 组合（Combinations）
• 子集（Subsets）
• 数独求解
• 单词搜索（Word Search）

JavaScript 示例：全排列

function permute(nums) {
  const result = [];
  const path = [];

  function backtrack() {
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }
    for (let num of nums) {
      if (path.includes(num)) continue; // 剪枝
      path.push(num);
      backtrack();
      path.pop(); // 回溯
    }
  }

  backtrack();
  return result;
}

console.log(permute([1, 2, 3]));

学习建议

掌握回溯算法的关键在于理解“状态树”的构建和“撤销选择”的时机。建议多练习 LeetCode 上的经典回溯题目，并画出递归调用栈辅助理解。