1. 搜索所有选择,及时排除不可能
先读递归。回溯用深度优先搜索枚举候选;路径记录已经作出的选择,进入下一层前修改状态,返回后撤销。只有证明当前前缀无法形成答案,才可以剪枝。
下面示例不修改输入,只用于可枚举的小规模数据,深递归会受调用栈限制;返回所有答案本身就可能消耗指数空间。
2. 子集:下一个位置只能向前
输入为互不相同的有限数值数组。每个路径都是一个子集,空输入有一个空子集。start 保证未来只选更靠后的下标,因此不会重复枚举不同顺序的同一集合。
function subsets(nums) {
const result = [];
const path = [];
function visit(start) {
result.push(path.slice());
for (let i = start; i < nums.length; i++) {
path.push(nums[i]);
visit(i + 1);
path.pop();
}
}
visit(0);
return result;
}必须复制路径,否则结果会引用同一个可变数组。结果数量为 2ⁿ,包含复制的时间和输出空间为 O(n·2ⁿ),不计输出的辅助空间为 O(n)。
3. 排列:已用位置不能再用
排列需要考虑不同顺序,所以不能仅令下标递增;使用标记记录当前路径已经用了哪些位置。输入仍要求值互不相同,空数组返回 [[]]。
function permute(nums) {
const result = [];
const path = [];
const used = new Array(nums.length).fill(false);
function visit() {
if (path.length === nums.length) {
result.push(path.slice());
return;
}
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true;
path.push(nums[i]);
visit();
path.pop();
used[i] = false;
}
}
visit();
return result;
}时间与输出空间为 O(n·n!),额外路径、标记和调用栈为 O(n)。若值可以重复,需先定义“按值去重还是按下标区分”,再增加同层去重规则,不能直接声称本实现无重复。
4. 皇后:用约束提前剪枝
约定 n 为非负整数,返回所有棋盘字符串数组,n = 0 约定一个空棋盘。逐行放一枚皇后,已占用的列、row - col 与 row + col 对角线不能再放。
function solveNQueens(n) {
const result = [];
const path = [];
const columns = new Set();
const descending = new Set();
const ascending = new Set();
function visit(row) {
if (row === n) {
result.push(path.map(col => '.'.repeat(col) + 'Q' + '.'.repeat(n - col - 1)));
return;
}
for (let col = 0; col < n; col++) {
if (columns.has(col) || descending.has(row - col) || ascending.has(row + col)) continue;
columns.add(col);
descending.add(row - col);
ascending.add(row + col);
path.push(col);
visit(row + 1);
path.pop();
columns.delete(col);
descending.delete(row - col);
ascending.delete(row + col);
}
}
visit(0);
return result;
}递归传 row + 1,不能使用 ++row 修改本层的行号而影响后续兄弟分支。按集合操作平均常数计费,搜索的宽松上界为 O(n·n!),另加 S 个答案各 n² 字符的输出成本;辅助状态为 O(n),输出空间为 O(Sn²)。
5. 验证与迁移
运行 node --test tests/algorithm-strategies-examples.test.mjs。检查子集数量和独立数组、排列的唯一性、皇后每行每列和对角线不冲突;n = 2、3 无解,n = 4 有 2 解。
闭卷练习:在子集上增加目标和约束。允许负数时,为什么不能看到当前和超过目标就停止?试用 [5,-2] 与目标 3。剪枝必须基于输入条件,不能仅凭直觉。
评论
正在加载评论…