> 回溯算法的核心在于通过深度优先搜索（DFS）与状态回退遍历问题的所有可能解 ### 通用模版 ```js function backtrack(choices, path, used) { // 终止条件：找到一个完整解 if (path.length === choices.length) { result.push([...path]); return; } // 遍历所有选择 for (let i = 0; i < choices.length; i++) { if (used[i]) continue; // 剪枝：跳过已用元素 used[i] = true; // 做选择 path.push(choices[i]); backtrack(choices, path, used); // 递归下一层 path.pop(); // 撤销选择 used[i] = false; } } ``` ### 交换法 ### 剪枝优化策略 ## 一、数组与双指针 ### 1. 两数之和（Two Sum） **问题**：在数组中找到两个数，使它们的和等于目标值。 **解法**：哈希表记录已遍历元素。 ```javascript var twoSum = function(nums, target) { const map = new Map(); for (let i = 0; i < nums.length; i++) { const complement = target - nums[i]; if (map.has(complement)) { return [map.get(complement), i]; } map.set(nums[i], i); } }; ``` ### 2. 三数之和（3Sum） **问题**：找出数组中所有不重复的三元组，使其和为0。 **解法**：排序 + 双指针。 ```javascript var threeSum = function(nums) { nums.sort((a, b) => a - b); const result = []; for (let i = 0; i < nums.length - 2; i++) { if (i > 0 && nums[i] === nums[i - 1]) continue; // 去重 let left = i + 1, right = nums.length - 1; while (left < right) { const sum = nums[i] + nums[left] + nums[right]; if (sum === 0) { result.push([nums[i], nums[left], nums[right]]); while (left < right && nums[left] === nums[left + 1]) left++; // 去重 while (left < right && nums[right] === nums[right - 1]) right--; left++; right--; } else if (sum < 0) { left++; } else { right--; } } } return result; }; ``` --- ## 二、动态规划 ### 1. 爬楼梯（Climbing Stairs） **问题**：每次爬1或2阶台阶，求爬到第 `n` 阶的方法数。 **状态转移**：`dp[i] = dp[i-1] + dp[i-2]`。 **空间优化**：用两个变量代替数组。 ```javascript var climbStairs = function(n) { if (n <= 2) return n; let a = 1, b = 2; for (let i = 3; i <= n; i++) { [a, b] = [b, a + b]; } return b; }; ``` ### 2. 打家劫舍（House Robber） **问题**：不能偷相邻房屋，求最大金额。 **状态转移**：`dp[i] = max(dp[i-1], dp[i-2] + nums[i])`。 ```javascript var rob = function(nums) { let prev = 0, curr = 0; for (const num of nums) { [prev, curr] = [curr, Math.max(curr, prev + num)]; } return curr; }; ``` --- ## 三、链表 ### 1. 反转链表（Reverse Linked List） **问题**：反转单链表。 **解法**：迭代法修改指针方向。 ```javascript var reverseList = function(head) { let prev = null, curr = head; while (curr) { const next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev; }; ``` ### 2. 合并两个有序链表（Merge Two Sorted Lists） **解法**：虚拟头节点简化边界处理。 ```javascript var mergeTwoLists = function(l1, l2) { const dummy = new ListNode(-1); let curr = dummy; while (l1 && l2) { if (l1.val < l2.val) { curr.next = l1; l1 = l1.next; } else { curr.next = l2; l2 = l2.next; } curr = curr.next; } curr.next = l1 || l2; return dummy.next; }; ``` --- ## 四、二叉树 ### 1. 二叉树的最大深度（Maximum Depth of Binary Tree） **解法**：递归分治。 ```javascript var maxDepth = function(root) { if (!root) return 0; return 1 + Math.max(maxDepth(root.left), maxDepth(root.right)); }; ``` ### 2. 二叉树的层序遍历（Binary Tree Level Order Traversal） **解法**：队列实现 BFS。 ```javascript var levelOrder = function(root) { if (!root) return []; const result = [], queue = [root]; while (queue.length) { const level = [], size = queue.length; for (let i = 0; i < size; i++) { const node = queue.shift(); level.push(node.val); if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } result.push(level); } return result; }; ``` --- ## 五、回溯与DFS ### 1. 全排列（Permutations） **解法**：回溯 + 路径记录。 ```javascript var permute = function(nums) { const result = []; const backtrack = (path, used) => { if (path.length === nums.length) { result.push([...path]); return; } for (let i = 0; i < nums.length; i++) { if (used[i]) continue; used[i] = true; path.push(nums[i]); backtrack(path, used); path.pop(); used[i] = false; } }; backtrack([], []); return result; }; ``` ### 2. 组合总和（Combination Sum） **解法**：排序剪枝 + 回溯。 ```javascript var combinationSum = function(candidates, target) { candidates.sort((a, b) => a - b); const result = []; const backtrack = (start, path, sum) => { if (sum === target) { result.push([...path]); return; } for (let i = start; i < candidates.length; i++) { if (sum + candidates[i] > target) break; // 剪枝 path.push(candidates[i]); backtrack(i, path, sum + candidates[i]); path.pop(); } }; backtrack(0, [], 0); return result; }; ``` --- ## 六、通用解题策略 ### 1. 动态规划问题四步法 - **定义状态**：明确 `dp[i]` 的含义。 - **状态转移方程**：推导递推关系。 - **初始条件**：设置初始值。 - **空间优化**：用变量替代数组（如滚动数组）。 ### 2. 回溯问题模板 - **路径**：记录已选择的值。 - **选择列表**：当前可选的元素。 - **终止条件**：满足条件时保存结果。 - **剪枝**：跳过无效分支（如重复元素去重）。 ### 3. 链表问题技巧 - **虚拟头节点**：简化头节点处理逻辑。 - **快慢指针**：解决环检测、中间节点等问题。 ### 0-1背包问题 **特点**：每个物品仅能选一次，需倒序遍历背包容量。 | 题号 | 题目名称 | 核心考点 | |------------|------------------------------|------------------------------| | **[416](https://leetcode.com/problems/partition-equal-subset-sum/)** | 分割等和子集 | 能否装满背包（布尔型DP） | | **[1049](https://leetcode.com/problems/last-stone-weight-ii/)** | 最后一块石头的重量 II | 背包最大价值（最接近 sum/2） | | **[494](https://leetcode.com/problems/target-sum/)** | 目标和 | 装满背包的方案数（组合数） | | **[474](https://leetcode.com/problems/ones-and-zeroes/)** | 一和零 | 二维费用背包（双重容量限制） | --- ### ♾️ **二、完全背包问题** **特点**：物品可无限选，需正序遍历背包容量。 | 题号 | 题目名称 | 核心考点 | |------------|------------------------------|------------------------------| | **[322](https://leetcode.com/problems/coin-change/)** | 零钱兑换 | 最小物品数（最值问题） | | **[518](https://leetcode.com/problems/coin-change-ii/)** | 零钱兑换 II | 组合数（顺序无关） | | **[377](https://leetcode.com/problems/combination-sum-iv/)** | 组合总和 Ⅳ | 排列数（顺序相关） | | **[279](https://leetcode.com/problems/perfect-squares/)** | 完全平方数 | 最小物品数（建模为平方数） | | **[139](https://leetcode.com/problems/word-break/)** | 单词拆分 | 布尔型DP（字符串分割） | --- ### 💡 **三、关键技巧总结** 1. **组合 vs 排列**： - **组合数**（顺序无关）：先遍历物品，再遍历背包（如 [518](https://leetcode.com/problems/coin-change-ii/)）。 - **排列数**（顺序相关）：先遍历背包，再遍历物品（如 [377](https://leetcode.com/problems/combination-sum-iv/)）。 2. **最值问题**： - 初始化 `dp` 为极大值（最小个数）或极小值（最大价值），边界 `dp[0]=0`。 3. **空间优化**： - 一维 `dp` 数组可覆盖多数场景，注意遍历方向（0-1背包倒序、完全背包正序）。 > 建议按分类顺序刷题，重点理解状态定义（`dp[i]` 含义）和转移方程。 ### 例子 | 问题类型 | 典型例题 | 常用算法 | 关键技巧 | |------------------------|--------------------|------------------|----------------------------| | 最优化问题 | 打家劫舍、爬楼梯 | 动态规划 | 状态压缩、贪心选择 | | 组合/排列 | 电话号码字母组合 | 回溯/DFS | 剪枝、路径记录 | | 子数组/子序列 | [最大子数组和](https://leetcode.cn/problems/maximum-subarray) | 动态规划/滑动窗口| 前缀和、状态定义 | | 图遍历 | 岛屿数量 | BFS/DFS | 访问标记、方向数组 | | 链表操作 | 反转链表 | 迭代/递归 | 双指针、虚拟头节点 |

LeetCode 热题 100 通用解题策略

AI 智能摘要

讨论与反馈

交流互动