回溯算法通过递归尝试所有可能路径，结合“做选择”与“撤销选择”实现深度优先搜索。其核心在于状态维护与及时回退，适用于全排列、子集等组合问题。JavaScript中利用递归和数组操作可轻松实现，关键注意结束条件、路径拷贝及选择列表更新。典型模板包含路径、选择列表和结果收集，确保每一步可逆且不遗漏解。
回溯算法是一种通过尝试解决问题的所有可能路径来寻找所有（或部分）解的算法。当发现当前路径不能得到解时，就“回退”到上一步，尝试其他路径。这种思想在JavaScript中可以通过递归和状态重置轻松实现。
回溯算法的核心思想
回溯的本质是深度优先搜索（DFS），结合了试探与撤销操作：
- 从一个初始状态出发，逐步构建解
- 每一步都尝试所有可选的选择
- 如果某条路径无法继续，就撤销最近的选择，回到之前的状态重新尝试
- 直到找到所有可行解或满足条件为止
基本模板（JavaScript版）
以下是一个通用的回溯算法结构：
function backtrack(path, options, result) {
// 满足结束条件
if (满足条件) {
result.push([...path]); // 注意：拷贝当前路径
return;
}
for (let i = 0; i < options.length; i++) {
// 做选择
path.push(options[i]);
// 进入下一层决策
backtrack(path, 新的选择列表, result);
// 撤销选择（回溯）
path.pop();
}
}
经典案例：全排列
给定一个没有重复数字的数组，返回其所有可能的全排列。
立即学习“Java免费学习笔记（深入）”；
function permute(nums) {
const result = [];
function backtrack(path, used) {
// 结束条件：路径长度等于原数组长度
if (path.length === nums.length) {
result.push([...path]);
return;
}
for (let num of nums) {
if (used.has(num)) continue;
// 做选择
path.push(num);
used.add(num);
// 进入下一层
backtrack(path, used);
// 撤销选择
path.pop();
used.delete(num);
}
}
backtrack([], new Set());
return result;
}
// 示例
console.log(permute([1, 2, 3]));
// 输出: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
另一个例子：子集问题
给定一个整数数组，返回所有可能的子集（幂集）。
function subsets(nums) {
const result = [];
function backtrack(start, path) {
// 每个节点都是有效解，直接加入
result.push([...path]);
for (let i = start; i < nums.length; i++) {
path.push(nums[i]); // 做选择
backtrack(i + 1, path); // 下一层从i+1开始避免重复
path.pop(); // 撤销选择
}
}
backtrack(0, []);
return result;
}
// 示例
console.log(subsets([1, 2, 3]));
// 输出: [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]
回溯算法的关键在于理解“做选择”和“撤销选择”的对称性。使用递归自然地保存了调用栈中的状态，而手动维护的路径变量需要在递归前后保持一致。只要掌握这个模式，大多数组合、排列、枚举类问题都可以迎刃而解。
基本上就这些，核心是递归结构 + 状态维护 + 及时回退。写的时候多注意边界条件和数据拷贝即可。
