回溯算法是一种通过探索所有可能的候选解来找出所有(或部分)解的算法。它常用于解决组合问题、排列问题、子集问题、棋盘问题等。
回溯 = 递归 + 剪枝。其基本思路是:
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 上的经典回溯题目,并画出递归调用栈辅助理解。