回溯算法本质就是在一棵决策树上做暴力穷举看似题型繁多、变化复杂实则有一套万能框架可以一网打尽。本文会用最直白的思路 可直接运行的 JS 代码带你从零吃透回溯子集、组合、排列、去重、可复选、数独、N 皇后全部覆盖。一、回溯算法核心框架站在回溯树的任意一个节点上你只需要想清楚 3 件事路径已经做出的选择选择列表当前还能做哪些选择结束条件到达底层无法再选择通用代码框架result [] def backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: # 做选择 将该选择从选择列表移除 路径.add(选择) backtrack(路径, 选择列表) # 撤销选择 路径.remove(选择) 将该选择再加入选择列表对应到多叉树遍历var traverse function (root) { for (var i 0; i root.children.length; i) { // 前序位置需要的操作 traverse(root.children[i]); // 后序位置需要的操作 } };二、经典例题实战46. 全排列无重不可复选用过的数字不能再用需要used标记。// 功能求数组 nums 的全排列所有不重复的排列组合 var permute function (nums) { // 1. 定义变量 const n nums.length; // 数组长度用来判断什么时候排列满了 const used new Array(n).fill(false); // 标记数字有没有被用过 // used [false, false, false] 表示 1、2、3 都没用过 const path []; // 路径当前正在拼的排列比如 [1,2] const res []; // 结果存放所有最终排列 // 2. 开始回溯 backtrack(); // 3. 返回结果 return res; // 回溯核心函数 function backtrack() { // 终止条件如果路径长度 数组长度说明排列完成 if (path.length n) { res.push([...path]); // 把当前排列放进结果浅拷贝 return; // 结束这层递归 } // 遍历所有数字挨个尝试选哪个数字 for (let i 0; i n; i) { // 如果这个数字已经用过了 → 跳过不能重复选 if (used[i]) continue; // 1. 做选择 path.push(nums[i]); // 把数字放进当前路径 used[i] true; // 标记这个数字我用过啦 // 2. 递归 // 继续选下一个数字进入下一层 backtrack(); // 3. 撤销选择回溯 used[i] false; // 取消标记这个数字可以被别人选了 path.pop(); // 把数字从路径里删掉 → 回到上一步 } } };n 位二进制数的所有可能每一位都可以选 0/1天然可复选。var generateBinaryNumber function (n) { // used[i][j] i表示第几步 j表示0 1 值表示是否使用 const used Array.from({ length: n }, () new Array(2).fill(false)); const res []; const path []; backtrack(); return res; function backtrack() { if (path.length n) { res.push([...path]); } const curStepIndex path.length; for (let i 0; i 1; i) { if (used[curStepIndex][i]) { continue; } path.push(i); used[curStepIndex][i] true; backtrack(); path.pop(); used[curStepIndex][i] false; } } };37. 解数独Hard暴力填数 剪枝找到解立刻返回。/** * param {character[][]} board * return {void} Do not return anything, modify board in-place instead. emptyList先把所有空格找出来按顺序填 三个Set快速判断数字能不能填剪枝 return true找到了一路向上终止递归 return false此路不通退回去换数字 */ // 功能解数独回溯算法 Hard 题 // 核心思想暴力枚举 剪枝 回溯选择 → 递归 → 撤销 var solveSudoku function (board) { // 存放所有空位置二维坐标[[行,列], [行,列]...] let emptyList []; const n 9; // 数独固定 9x9 // 三个 Set 用来快速判断数字是否在 行/列/九宫格 中出现过 // rowIdxToVaList[row] 表示第 row 行已经有哪些数字 const rowIdxToVaList new Array(n).fill(0).map(() new Set()); // colIdxToVaList[col] 表示第 col 列已经有哪些数字 const colIdxToVaList new Array(n).fill(0).map(() new Set()); // gridIdxToVaList[gridIdx] 表示第几个 3x3 九宫格已经有哪些数字 const gridIdxToVaList new Array(n).fill(0).map(() new Set()); // 工具函数计算 (row, col) 属于第几个 3x3 九宫格0~8 // 原理把 9 个九宫格看成 3x3 矩阵 → 二维转一维 const getGridIdx (row, col) { return Math.floor(row / 3) * 3 Math.floor(col / 3); }; // 第一步初始化棋盘 // 遍历整个 9x9 数独 for (let row 0; row n; row) { for (let col 0; col n; col) { // 如果当前位置是空的记录坐标 if (board[row][col] .) { emptyList.push([row, col]); continue; } // 把棋盘上的字符串数字转成 Number 类型 const curVal Number(board[row][col]); // 获取当前位置属于哪个九宫格 const gridIdx getGridIdx(row, col); // 把数字分别加入 行、列、九宫格 的 Set 中 rowIdxToVaList[row].add(curVal); colIdxToVaList[col].add(curVal); gridIdxToVaList[gridIdx].add(curVal); } } // 空格总数用来判断什么时候填完 const emptyCount emptyList.length; // 当前正在填第几个空格从第 0 个开始 let curEmptyIdx 0; // 开始回溯 backtrack(); return; // 核心回溯函数 // 返回值boolean // true 找到解了直接终止所有递归 // false 此路不通需要回溯 function backtrack() { // 终止条件当前已经填完了所有空格 → 找到唯一解 if (curEmptyIdx emptyCount) { return true; } // 取出当前要填的空格坐标行、列 const [row, col] emptyList[curEmptyIdx]; // 计算当前空格属于哪个九宫格 const gridIdx getGridIdx(row, col); // 尝试往这个空格填入 1~9 for (let i 1; i 9; i) { const curVal i; // 剪枝 // 如果这个数字在 行、列、九宫格 中已经存在 → 跳过不能填 if ( rowIdxToVaList[row].has(curVal) || colIdxToVaList[col].has(curVal) || gridIdxToVaList[gridIdx].has(curVal) ) { continue; } // 1. 做选择 // 往数独棋盘填入数字 board[row][col] i ; // 把这个数字标记为已使用 rowIdxToVaList[row].add(curVal); colIdxToVaList[col].add(curVal); gridIdxToVaList[gridIdx].add(curVal); // 准备填下一个空格 curEmptyIdx; // 2. 递归填下一个空格 // 接收下一层递归的返回值 const isFound backtrack(); // 如果下一层返回 true → 说明后面全部填完了找到解了 if (isFound) { return true; // 一路向上 return true直接结束所有递归 } // 3. 撤销选择回溯核心 // 代码走到这里 刚才填的数字不对后面走不通了 // 把数字从棋盘擦掉 board[row][col] .; // 从 Set 中删除取消标记 rowIdxToVaList[row].delete(curVal); colIdxToVaList[col].delete(curVal); gridIdxToVaList[gridIdx].delete(curVal); // 回到当前这个空格继续尝试下一个数字 curEmptyIdx--; } // 4. 所有数字都试过了都不行 // 说明上一步填错了 → 返回 false让上一层回溯 return false; } };51. N 皇后Hard按行放置标记列和两条斜线即可。var solveNQueens function (n) { const res []; // 存放所有解法 // 标记列是否被占用 const colUsed new Array(n).fill(false); // 标记左上 - 右下 斜线row col const leftTopUsed new Array(2 * n - 1).fill(false); // 标记右上 - 左下 斜线row - col n -1 const rightBottomTopUsed new Array(2 * n - 1).fill(false); const path []; // 记录每一行皇后放在第几列 // 从第 0 行开始放 backtrack(0); return res; // 回溯核心 function backtrack(curRow) { // 终止条件所有行都放完皇后 → 得到一个解 if (curRow n) { // 转换成要求的输出格式 res.push([...path].map(id ..repeat(id) Q ..repeat(n - id - 1))); return; // 找到解向上传递停止递归 } // 尝试在当前行的每一列放皇后 for (let col 0; col n; col) { // 计算当前位置所在的两条斜线 ID const ltId curRow col; const rbId curRow - col n - 1; // 剪枝列 / 斜线 任意一个被占用都不能放 if (colUsed[col] || leftTopUsed[ltId] || rightBottomTopUsed[rbId]) { continue; } // 1. 做选择 path.push(col); colUsed[col] true; leftTopUsed[ltId] true; rightBottomTopUsed[rbId] true; // 2. 递归放下一行 backtrack(curRow 1); // const canFill backtrack(curRow 1); // if (canFill) return true; // 找到解直接返回 // 3. 撤销选择回溯 path.pop(); colUsed[col] false; leftTopUsed[ltId] false; rightBottomTopUsed[rbId] false; } // 当前行所有列都不行 → 回溯 return; } };三、排列组合子集三大变体从数组中按规则取元素一共 3 种核心变体无重不可复选元素唯一只能用一次可重不可复选元素可重复只能用一次无重可复选元素唯一可用多次四、子集/组合/排列 全题型代码1. 子集无重不可复选78每个节点都是一个子集进来就收集。// 核心思想回溯 不回头只能往后选避免重复 var subsets function (nums) { // 数组长度比如 [1,2,3] 长度是 3 const n nums.length; // res存放最终所有子集答案 const res []; // path记录当前正在拼接的子集路径 const path []; // 从第 0 个元素开始选 backtrack(0); // 返回所有子集 return res; // 回溯核心函数 // start表示从哪个索引开始选保证只能往后不回头 表示可选择的元素 function backtrack(start) { // ✅ 关键每个节点都是一个子集进来就先收集 // [...path] 是拷贝一份防止原数组被修改 res.push([...path]); // 循环从 start 开始往后选绝对不回头 // i 是当前选中的元素索引 for (let i start; i n; i) { // 1. 做选择把当前元素放进子集 path.push(nums[i]); // 2. 递归继续往下选只能从 i1 开始不回头 backtrack(i 1); // 3. 撤销选择回溯把刚才放进去的元素拿掉 // 回到上一步尝试下一个元素 path.pop(); } } };2. 组合无重不可复选长度够了才收集直接剪枝。// 核心思想回溯 不回头只能往后选避免重复 var combine function (nums) { // 数组长度比如 [1,2,3] 长度是 3 const n nums.length; // res存放最终所有子集答案 const res []; // path记录当前正在拼接的子集路径 const path []; // 从第 0 个元素开始选 backtrack(0); // 返回所有子集 return res; // 回溯核心函数 // start表示从哪个索引开始选保证只能往后不回头 表示可选择的元素 function backtrack(start) { // 就这里改下长度够了收集就行 if (path.length n) { res.push([...path]); return; } // 循环从 start 开始往后选绝对不回头 // i 是当前选中的元素索引 for (let i start; i n; i) { // 1. 做选择把当前元素放进子集 path.push(nums[i]); // 2. 递归继续往下选只能从 i1 开始不回头 backtrack(i 1); // 3. 撤销选择回溯把刚才放进去的元素拿掉 // 回到上一步尝试下一个元素 path.pop(); } } };77. 组合从 1~n 选 k 个// LeetCode 77. 组合从 1~n 中选出 k 个数的所有组合 // 核心子集的微改版 → 长度够 k 才收集 var combine function (n, k) { // 存放最终所有组合结果 const res []; // 记录当前正在拼接的路径 const path []; // 从数字 1 开始选 backtrack(1); return res; // 回溯核心 // start从哪个数字开始选保证不回头、不重复 function backtrack(start) { // 核心区别只有路径长度达到 k才收集结果 if (path.length k) { res.push([...path]); return; // 剪枝已经够长了不用继续往下递归 } // 只能从 start 往后选绝对不回头 for (let i start; i n; i) { // 1. 选择当前数字 path.push(i); // 2. 递归下一个数字只能从 i1 开始选 backtrack(i 1); // 3. 撤销选择回溯 path.pop(); } } };3. 子集/组合可重不可复选90先排序同层相同数字跳过。// 核心思想回溯 不回头只能往后选避免重复 var subsets function (nums) { // 这里加个排序相同的就在一起 nums.sort((x, y) x - y); // 数组长度比如 [1,2,3] 长度是 3 const n nums.length; // res存放最终所有子集答案 const res []; // path记录当前正在拼接的子集路径 const path []; // 从第 0 个元素开始选 backtrack(0); // 返回所有子集 return res; // 回溯核心函数 // start表示从哪个索引开始选保证只能往后不回头 表示可选择的元素 function backtrack(start) { // 切换子集和组合题的关键 // res.push([...path]); // 组合的话就是长度够了收集 然后不用往下走了 if (path.length n) { res.push([...path]); return; } // 循环从 start 开始往后选绝对不回头 // i 是当前选中的元素索引 for (let i start; i n; i) { // 这里同一层相同的跳过 if (i start nums[i] nums[i - 1]) continue; // 1. 做选择把当前元素放进子集 path.push(nums[i]); // 2. 递归继续往下选只能从 i1 开始不回头 backtrack(i 1); // 3. 撤销选择回溯把刚才放进去的元素拿掉 // 回到上一步尝试下一个元素 path.pop(); } } };4. 排列可重不可复选47排序 !used[i-1]只跳过同层重复。var permute function (nums) { // 这里加个排序相同的就在一起 nums.sort((x, y) x - y); const n nums.length; const used new Array(n).fill(false); // ✅ 标记用过没 const res []; const path []; backtrack(); return res; function backtrack() { // 长度够了才收集 if (path.length n) { res.push([...path]); return; } // ✅ 排列核心每次从头开始选i0 for (let i 0; i n; i) { if (used[i]) continue; // ✅ 用过就跳过 // used[i - 1] false表示前一个相同数字刚在【同一层】用完、撤销了。想象 1 2 2 第一个2使用完之后used[2]false 第二个2需要跳过 if (i 0 nums[i] nums[i - 1] used[i - 1] false) continue; path.push(nums[i]); used[i] true; // ✅ 标记使用 backtrack(); // ✅ 继续递归 path.pop(); // ✅ 撤销 used[i] false; // ✅ 取消标记 } } };5. 组合总和无重可复选39可以重复选自己递归传i。var combinationSum function (candidates, target) { const n candidates.length; const res []; let curSum 0; const path []; // 不重复的 就索引既定因为前面的数字的情况已经尝试完了 backtrack(0); return res; function backtrack(start) { // 条件达到 收 if (curSum target) { res.push([...path]); return; } // 和大于的话 也不用走了 死路一条 if (curSum target) { return; } for (let i start; i n; i) { const cur candidates[i]; // 选择 path.push(cur); curSum cur; // 继续往下这条路往下找到了 往后 死路了也往回 因为可以复选 所以从自己开始。这是i本身就在往后走了。 backtrack(i); // 但是这里表示这个数字完事了 换下一个 path.pop(); curSum - cur; } } };推荐写法curSum用参数传递更干净。var combinationSum function (candidates, target) { const n candidates.length; const res []; let curSum 0; const path []; // 不重复的 就索引既定因为前面的数字的情况已经尝试完了 backtrack(0, 0); return res; function backtrack(start, curSum) { // 条件达到 收 if (curSum target) { res.push([...path]); return; } // 和大于的话 也不用走了 死路一条 if (curSum target) { return; } for (let i start; i n; i) { const cur candidates[i]; // 选择 path.push(cur); // 继续往下这条路往下找到了 往后 死路了也往回 因为可以复选 所以从自己开始。这是i本身就在往后走了。 backtrack(i, curSum cur); // 但是这里表示这个数字完事了 换下一个 path.pop(); } } };6. 排列无重可复选可复选 → 不需要used。// 排列用过的就不能用了没用过的都能选 var permute function (nums) { // 名字改对就行 const n nums.length; // const used new Array(n).fill(false); // ✅ 标记用过没 const res []; const path []; backtrack(); return res; function backtrack() { // 长度够了才收集 if (path.length n) { res.push([...path]); return; } // ✅ 排列核心每次从头开始选i0 for (let i 0; i n; i) { // if (used[i]) continue; // ✅ 用过就跳过 path.push(nums[i]); // used[i] true; // ✅ 标记使用 backtrack(); // ✅ 继续递归 path.pop(); // ✅ 撤销 // used[i] false; // ✅ 取消标记 } } };五、核心总结子集/组合用start不回头避免重复组合排列从头遍历用used防重元素可重排序 同层去重可复选递归传i不用used路径数组用push pop数字可传参掌握这套思路LeetCode 所有回溯题都可以直接套框架秒杀。
吃透回溯算法：从框架到实战
回溯算法本质就是在一棵决策树上做暴力穷举看似题型繁多、变化复杂实则有一套万能框架可以一网打尽。本文会用最直白的思路 可直接运行的 JS 代码带你从零吃透回溯子集、组合、排列、去重、可复选、数独、N 皇后全部覆盖。一、回溯算法核心框架站在回溯树的任意一个节点上你只需要想清楚 3 件事路径已经做出的选择选择列表当前还能做哪些选择结束条件到达底层无法再选择通用代码框架result [] def backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: # 做选择 将该选择从选择列表移除 路径.add(选择) backtrack(路径, 选择列表) # 撤销选择 路径.remove(选择) 将该选择再加入选择列表对应到多叉树遍历var traverse function (root) { for (var i 0; i root.children.length; i) { // 前序位置需要的操作 traverse(root.children[i]); // 后序位置需要的操作 } };二、经典例题实战46. 全排列无重不可复选用过的数字不能再用需要used标记。// 功能求数组 nums 的全排列所有不重复的排列组合 var permute function (nums) { // 1. 定义变量 const n nums.length; // 数组长度用来判断什么时候排列满了 const used new Array(n).fill(false); // 标记数字有没有被用过 // used [false, false, false] 表示 1、2、3 都没用过 const path []; // 路径当前正在拼的排列比如 [1,2] const res []; // 结果存放所有最终排列 // 2. 开始回溯 backtrack(); // 3. 返回结果 return res; // 回溯核心函数 function backtrack() { // 终止条件如果路径长度 数组长度说明排列完成 if (path.length n) { res.push([...path]); // 把当前排列放进结果浅拷贝 return; // 结束这层递归 } // 遍历所有数字挨个尝试选哪个数字 for (let i 0; i n; i) { // 如果这个数字已经用过了 → 跳过不能重复选 if (used[i]) continue; // 1. 做选择 path.push(nums[i]); // 把数字放进当前路径 used[i] true; // 标记这个数字我用过啦 // 2. 递归 // 继续选下一个数字进入下一层 backtrack(); // 3. 撤销选择回溯 used[i] false; // 取消标记这个数字可以被别人选了 path.pop(); // 把数字从路径里删掉 → 回到上一步 } } };n 位二进制数的所有可能每一位都可以选 0/1天然可复选。var generateBinaryNumber function (n) { // used[i][j] i表示第几步 j表示0 1 值表示是否使用 const used Array.from({ length: n }, () new Array(2).fill(false)); const res []; const path []; backtrack(); return res; function backtrack() { if (path.length n) { res.push([...path]); } const curStepIndex path.length; for (let i 0; i 1; i) { if (used[curStepIndex][i]) { continue; } path.push(i); used[curStepIndex][i] true; backtrack(); path.pop(); used[curStepIndex][i] false; } } };37. 解数独Hard暴力填数 剪枝找到解立刻返回。/** * param {character[][]} board * return {void} Do not return anything, modify board in-place instead. emptyList先把所有空格找出来按顺序填 三个Set快速判断数字能不能填剪枝 return true找到了一路向上终止递归 return false此路不通退回去换数字 */ // 功能解数独回溯算法 Hard 题 // 核心思想暴力枚举 剪枝 回溯选择 → 递归 → 撤销 var solveSudoku function (board) { // 存放所有空位置二维坐标[[行,列], [行,列]...] let emptyList []; const n 9; // 数独固定 9x9 // 三个 Set 用来快速判断数字是否在 行/列/九宫格 中出现过 // rowIdxToVaList[row] 表示第 row 行已经有哪些数字 const rowIdxToVaList new Array(n).fill(0).map(() new Set()); // colIdxToVaList[col] 表示第 col 列已经有哪些数字 const colIdxToVaList new Array(n).fill(0).map(() new Set()); // gridIdxToVaList[gridIdx] 表示第几个 3x3 九宫格已经有哪些数字 const gridIdxToVaList new Array(n).fill(0).map(() new Set()); // 工具函数计算 (row, col) 属于第几个 3x3 九宫格0~8 // 原理把 9 个九宫格看成 3x3 矩阵 → 二维转一维 const getGridIdx (row, col) { return Math.floor(row / 3) * 3 Math.floor(col / 3); }; // 第一步初始化棋盘 // 遍历整个 9x9 数独 for (let row 0; row n; row) { for (let col 0; col n; col) { // 如果当前位置是空的记录坐标 if (board[row][col] .) { emptyList.push([row, col]); continue; } // 把棋盘上的字符串数字转成 Number 类型 const curVal Number(board[row][col]); // 获取当前位置属于哪个九宫格 const gridIdx getGridIdx(row, col); // 把数字分别加入 行、列、九宫格 的 Set 中 rowIdxToVaList[row].add(curVal); colIdxToVaList[col].add(curVal); gridIdxToVaList[gridIdx].add(curVal); } } // 空格总数用来判断什么时候填完 const emptyCount emptyList.length; // 当前正在填第几个空格从第 0 个开始 let curEmptyIdx 0; // 开始回溯 backtrack(); return; // 核心回溯函数 // 返回值boolean // true 找到解了直接终止所有递归 // false 此路不通需要回溯 function backtrack() { // 终止条件当前已经填完了所有空格 → 找到唯一解 if (curEmptyIdx emptyCount) { return true; } // 取出当前要填的空格坐标行、列 const [row, col] emptyList[curEmptyIdx]; // 计算当前空格属于哪个九宫格 const gridIdx getGridIdx(row, col); // 尝试往这个空格填入 1~9 for (let i 1; i 9; i) { const curVal i; // 剪枝 // 如果这个数字在 行、列、九宫格 中已经存在 → 跳过不能填 if ( rowIdxToVaList[row].has(curVal) || colIdxToVaList[col].has(curVal) || gridIdxToVaList[gridIdx].has(curVal) ) { continue; } // 1. 做选择 // 往数独棋盘填入数字 board[row][col] i ; // 把这个数字标记为已使用 rowIdxToVaList[row].add(curVal); colIdxToVaList[col].add(curVal); gridIdxToVaList[gridIdx].add(curVal); // 准备填下一个空格 curEmptyIdx; // 2. 递归填下一个空格 // 接收下一层递归的返回值 const isFound backtrack(); // 如果下一层返回 true → 说明后面全部填完了找到解了 if (isFound) { return true; // 一路向上 return true直接结束所有递归 } // 3. 撤销选择回溯核心 // 代码走到这里 刚才填的数字不对后面走不通了 // 把数字从棋盘擦掉 board[row][col] .; // 从 Set 中删除取消标记 rowIdxToVaList[row].delete(curVal); colIdxToVaList[col].delete(curVal); gridIdxToVaList[gridIdx].delete(curVal); // 回到当前这个空格继续尝试下一个数字 curEmptyIdx--; } // 4. 所有数字都试过了都不行 // 说明上一步填错了 → 返回 false让上一层回溯 return false; } };51. N 皇后Hard按行放置标记列和两条斜线即可。var solveNQueens function (n) { const res []; // 存放所有解法 // 标记列是否被占用 const colUsed new Array(n).fill(false); // 标记左上 - 右下 斜线row col const leftTopUsed new Array(2 * n - 1).fill(false); // 标记右上 - 左下 斜线row - col n -1 const rightBottomTopUsed new Array(2 * n - 1).fill(false); const path []; // 记录每一行皇后放在第几列 // 从第 0 行开始放 backtrack(0); return res; // 回溯核心 function backtrack(curRow) { // 终止条件所有行都放完皇后 → 得到一个解 if (curRow n) { // 转换成要求的输出格式 res.push([...path].map(id ..repeat(id) Q ..repeat(n - id - 1))); return; // 找到解向上传递停止递归 } // 尝试在当前行的每一列放皇后 for (let col 0; col n; col) { // 计算当前位置所在的两条斜线 ID const ltId curRow col; const rbId curRow - col n - 1; // 剪枝列 / 斜线 任意一个被占用都不能放 if (colUsed[col] || leftTopUsed[ltId] || rightBottomTopUsed[rbId]) { continue; } // 1. 做选择 path.push(col); colUsed[col] true; leftTopUsed[ltId] true; rightBottomTopUsed[rbId] true; // 2. 递归放下一行 backtrack(curRow 1); // const canFill backtrack(curRow 1); // if (canFill) return true; // 找到解直接返回 // 3. 撤销选择回溯 path.pop(); colUsed[col] false; leftTopUsed[ltId] false; rightBottomTopUsed[rbId] false; } // 当前行所有列都不行 → 回溯 return; } };三、排列组合子集三大变体从数组中按规则取元素一共 3 种核心变体无重不可复选元素唯一只能用一次可重不可复选元素可重复只能用一次无重可复选元素唯一可用多次四、子集/组合/排列 全题型代码1. 子集无重不可复选78每个节点都是一个子集进来就收集。// 核心思想回溯 不回头只能往后选避免重复 var subsets function (nums) { // 数组长度比如 [1,2,3] 长度是 3 const n nums.length; // res存放最终所有子集答案 const res []; // path记录当前正在拼接的子集路径 const path []; // 从第 0 个元素开始选 backtrack(0); // 返回所有子集 return res; // 回溯核心函数 // start表示从哪个索引开始选保证只能往后不回头 表示可选择的元素 function backtrack(start) { // ✅ 关键每个节点都是一个子集进来就先收集 // [...path] 是拷贝一份防止原数组被修改 res.push([...path]); // 循环从 start 开始往后选绝对不回头 // i 是当前选中的元素索引 for (let i start; i n; i) { // 1. 做选择把当前元素放进子集 path.push(nums[i]); // 2. 递归继续往下选只能从 i1 开始不回头 backtrack(i 1); // 3. 撤销选择回溯把刚才放进去的元素拿掉 // 回到上一步尝试下一个元素 path.pop(); } } };2. 组合无重不可复选长度够了才收集直接剪枝。// 核心思想回溯 不回头只能往后选避免重复 var combine function (nums) { // 数组长度比如 [1,2,3] 长度是 3 const n nums.length; // res存放最终所有子集答案 const res []; // path记录当前正在拼接的子集路径 const path []; // 从第 0 个元素开始选 backtrack(0); // 返回所有子集 return res; // 回溯核心函数 // start表示从哪个索引开始选保证只能往后不回头 表示可选择的元素 function backtrack(start) { // 就这里改下长度够了收集就行 if (path.length n) { res.push([...path]); return; } // 循环从 start 开始往后选绝对不回头 // i 是当前选中的元素索引 for (let i start; i n; i) { // 1. 做选择把当前元素放进子集 path.push(nums[i]); // 2. 递归继续往下选只能从 i1 开始不回头 backtrack(i 1); // 3. 撤销选择回溯把刚才放进去的元素拿掉 // 回到上一步尝试下一个元素 path.pop(); } } };77. 组合从 1~n 选 k 个// LeetCode 77. 组合从 1~n 中选出 k 个数的所有组合 // 核心子集的微改版 → 长度够 k 才收集 var combine function (n, k) { // 存放最终所有组合结果 const res []; // 记录当前正在拼接的路径 const path []; // 从数字 1 开始选 backtrack(1); return res; // 回溯核心 // start从哪个数字开始选保证不回头、不重复 function backtrack(start) { // 核心区别只有路径长度达到 k才收集结果 if (path.length k) { res.push([...path]); return; // 剪枝已经够长了不用继续往下递归 } // 只能从 start 往后选绝对不回头 for (let i start; i n; i) { // 1. 选择当前数字 path.push(i); // 2. 递归下一个数字只能从 i1 开始选 backtrack(i 1); // 3. 撤销选择回溯 path.pop(); } } };3. 子集/组合可重不可复选90先排序同层相同数字跳过。// 核心思想回溯 不回头只能往后选避免重复 var subsets function (nums) { // 这里加个排序相同的就在一起 nums.sort((x, y) x - y); // 数组长度比如 [1,2,3] 长度是 3 const n nums.length; // res存放最终所有子集答案 const res []; // path记录当前正在拼接的子集路径 const path []; // 从第 0 个元素开始选 backtrack(0); // 返回所有子集 return res; // 回溯核心函数 // start表示从哪个索引开始选保证只能往后不回头 表示可选择的元素 function backtrack(start) { // 切换子集和组合题的关键 // res.push([...path]); // 组合的话就是长度够了收集 然后不用往下走了 if (path.length n) { res.push([...path]); return; } // 循环从 start 开始往后选绝对不回头 // i 是当前选中的元素索引 for (let i start; i n; i) { // 这里同一层相同的跳过 if (i start nums[i] nums[i - 1]) continue; // 1. 做选择把当前元素放进子集 path.push(nums[i]); // 2. 递归继续往下选只能从 i1 开始不回头 backtrack(i 1); // 3. 撤销选择回溯把刚才放进去的元素拿掉 // 回到上一步尝试下一个元素 path.pop(); } } };4. 排列可重不可复选47排序 !used[i-1]只跳过同层重复。var permute function (nums) { // 这里加个排序相同的就在一起 nums.sort((x, y) x - y); const n nums.length; const used new Array(n).fill(false); // ✅ 标记用过没 const res []; const path []; backtrack(); return res; function backtrack() { // 长度够了才收集 if (path.length n) { res.push([...path]); return; } // ✅ 排列核心每次从头开始选i0 for (let i 0; i n; i) { if (used[i]) continue; // ✅ 用过就跳过 // used[i - 1] false表示前一个相同数字刚在【同一层】用完、撤销了。想象 1 2 2 第一个2使用完之后used[2]false 第二个2需要跳过 if (i 0 nums[i] nums[i - 1] used[i - 1] false) continue; path.push(nums[i]); used[i] true; // ✅ 标记使用 backtrack(); // ✅ 继续递归 path.pop(); // ✅ 撤销 used[i] false; // ✅ 取消标记 } } };5. 组合总和无重可复选39可以重复选自己递归传i。var combinationSum function (candidates, target) { const n candidates.length; const res []; let curSum 0; const path []; // 不重复的 就索引既定因为前面的数字的情况已经尝试完了 backtrack(0); return res; function backtrack(start) { // 条件达到 收 if (curSum target) { res.push([...path]); return; } // 和大于的话 也不用走了 死路一条 if (curSum target) { return; } for (let i start; i n; i) { const cur candidates[i]; // 选择 path.push(cur); curSum cur; // 继续往下这条路往下找到了 往后 死路了也往回 因为可以复选 所以从自己开始。这是i本身就在往后走了。 backtrack(i); // 但是这里表示这个数字完事了 换下一个 path.pop(); curSum - cur; } } };推荐写法curSum用参数传递更干净。var combinationSum function (candidates, target) { const n candidates.length; const res []; let curSum 0; const path []; // 不重复的 就索引既定因为前面的数字的情况已经尝试完了 backtrack(0, 0); return res; function backtrack(start, curSum) { // 条件达到 收 if (curSum target) { res.push([...path]); return; } // 和大于的话 也不用走了 死路一条 if (curSum target) { return; } for (let i start; i n; i) { const cur candidates[i]; // 选择 path.push(cur); // 继续往下这条路往下找到了 往后 死路了也往回 因为可以复选 所以从自己开始。这是i本身就在往后走了。 backtrack(i, curSum cur); // 但是这里表示这个数字完事了 换下一个 path.pop(); } } };6. 排列无重可复选可复选 → 不需要used。// 排列用过的就不能用了没用过的都能选 var permute function (nums) { // 名字改对就行 const n nums.length; // const used new Array(n).fill(false); // ✅ 标记用过没 const res []; const path []; backtrack(); return res; function backtrack() { // 长度够了才收集 if (path.length n) { res.push([...path]); return; } // ✅ 排列核心每次从头开始选i0 for (let i 0; i n; i) { // if (used[i]) continue; // ✅ 用过就跳过 path.push(nums[i]); // used[i] true; // ✅ 标记使用 backtrack(); // ✅ 继续递归 path.pop(); // ✅ 撤销 // used[i] false; // ✅ 取消标记 } } };五、核心总结子集/组合用start不回头避免重复组合排列从头遍历用used防重元素可重排序 同层去重可复选递归传i不用used路径数组用push pop数字可传参掌握这套思路LeetCode 所有回溯题都可以直接套框架秒杀。
