感谢阅读本文 · 欢迎在下方留言交流你的想法
探索更多文章 →共 0 条
回溯算法的核心在于通过深度优先搜索（DFS）与状态回退遍历问题的所有可能解
jsfunction 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; } }
问题：在数组中找到两个数，使它们的和等于目标值。
解法：哈希表记录已遍历元素。
javascriptvar 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); } };
问题：找出数组中所有不重复的三元组，使其和为0。
解法：排序 + 双指针。
javascript
问题：每次爬1或2阶台阶，求爬到第 n 阶的方法数。
状态转移：dp[i] = dp[i-1] + dp[i-2]。
空间优化：用两个变量代替数组。
javascript
问题：不能偷相邻房屋，求最大金额。
状态转移：dp[i] = max(dp[i-1], dp[i-2] + nums[i])。
javascript
问题：反转单链表。
解法：迭代法修改指针方向。
javascript
解法：虚拟头节点简化边界处理。
javascript
解法：递归分治。
javascript
解法：队列实现 BFS。
javascript
解法：回溯 + 路径记录。
javascript
解法：排序剪枝 + 回溯。
javascript
dp[i] 的含义。特点：每个物品仅能选一次，需倒序遍历背包容量。
| 题号 | 题目名称 | 核心考点 |
|---|---|---|
| 416 | 分割等和子集 | 能否装满背包（布尔型DP） |
| 1049 | 最后一块石头的重量 II | 背包最大价值（最接近 sum/2） |
| 494 | 目标和 | 装满背包的方案数（组合数） |
| 474 | 一和零 | 二维费用背包（双重容量限制） |
特点：物品可无限选，需正序遍历背包容量。
| 题号 | 题目名称 | 核心考点 |
|---|---|---|
| 322 | 零钱兑换 | 最小物品数（最值问题） |
| 518 | 零钱兑换 II | 组合数（顺序无关） |
| 377 | 组合总和 Ⅳ | 排列数（顺序相关） |
| 279 | 完全平方数 | 最小物品数（建模为平方数） |
| 139 | 单词拆分 | 布尔型DP（字符串分割） |
dp 为极大值（最小个数）或极小值（最大价值），边界 dp[0]=0。dp 数组可覆盖多数场景，注意遍历方向（0-1背包倒序、完全背包正序）。建议按分类顺序刷题，重点理解状态定义（
dp[i]含义）和转移方程。
| 问题类型 | 典型例题 | 常用算法 | 关键技巧 |
|---|---|---|---|
| 最优化问题 | 打家劫舍、爬楼梯 | 动态规划 | 状态压缩、贪心选择 |
| 组合/排列 | 电话号码字母组合 | 回溯/DFS | 剪枝、路径记录 |
| 子数组/子序列 | 最大子数组和 | 动态规划/滑动窗口 | 前缀和、状态定义 |
| 图遍历 | 岛屿数量 | BFS/DFS | 访问标记、方向数组 |
| 链表操作 | 反转链表 | 迭代/递归 | 双指针、虚拟头节点 |
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;
};
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;
};
var rob = function(nums) {
let prev = 0, curr = 0;
for (const num of nums) {
[prev, curr] = [curr, Math.max(curr, prev + num)];
}
return curr;
};
var reverseList = function(head) {
let prev = null, curr = head;
while (curr) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
};
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;
};
var maxDepth = function(root) {
if (!root) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
};
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;
};
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;
};
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;
};