代码随想录算法训练营第25天｜回溯算法Part04

记录题目：

• 重新安排行程
• N 皇后
• 解数独

---

给定一个机票的字符串二维数组 tickets，
其中 tickets[i] = [from, to] 表示从 from 到 to 的航班信息。
从 "JFK" 机场出发，返回重新安排后的行程，
行程按字典序排列且恰好使用所有机票一次。

LeetCode332. 重新安排行程

• N 叉树

• Hierholzer 算法

var findItinerary = function (tickets) {
    const result = ['JFK'], map = {};
    // 构建邻接表
    for (const [from, to] of tickets) {
        if (!map[from]) {
            map[from] = [];
        }
        map[from].push(to);
    }
    // 将目的地按字典序排序
    for (const city in map) {
        map[city].sort();
    }
    function backtracking() {
        // 如果结果已包含所有航班（n 个票，对应 n + 1 个机场）
        if (result.length === tickets.length + 1) {
            return true;
        }
        const lastCity = result[result.length - 1];
        const destinations = map[lastCity];
        if (!destinations || destinations.length === 0) {
            return false;
        }
        for (let i = 0; i < destinations.length; i++) {
            const nextCity = destinations[i];
            // 移除当前航线（表示已使用）
            destinations.splice(i, 1);
            result.push(nextCity);
            if (backtracking()) return true;
            // 回溯：撤销操作
            result.pop();
            destinations.splice(i, 0, nextCity);
        }
        return false;
    }
    backtracking();
    return result;
};

如果当前路径成功走完（用了所有票），就 return true，一路向上传递终止； 如果当前路径走死了，就 return false，上一层回退换一条路走。

方法：slice(start, end)

属性	描述
参数形式	截取索引 [start, end) 之间的元素（不含 end）
主要作用	复制子数组
返回值	新数组
是否修改原数组	否

方法：splice(start, deleteCount, ...itemsToAdd)

属性	描述
参数形式	从索引 start 开始，删除 deleteCount 个元素， 并插入 itemsToAdd（可选）
主要作用	删除或插入元素
返回值	被删除的元素组成的新数组
是否修改原数组	是

function findItinerary(tickets) {
    // 邻接表：记录每个起点对应的目的地列表（按字典序排序）
    const graph = new Map();
    // 建图
    for (const [from, to] of tickets) {
        if (!graph.has(from)) {
            graph.set(from, []);
        }
        graph.get(from).push(to);
    }
    // 对每个出发点的目的地列表进行字典序排序（小的在前）
    for (const [from, tos] of graph.entries()) {
        tos.sort(); // sort 默认就是字典序
    }
    const itinerary = [];
    // 深度优先遍历（Hierholzer 核心）
    function dfs(from) {
        const destinations = graph.get(from) || [];
        // 一直走到没有可去的目的地为止（贪心优先选字典序小的）
        while (destinations.length > 0) {
            // 移除最小字典序的目的地并前进
            const next = destinations.shift();
            dfs(next);
        }
        // 回退时将当前节点加入结果（注意：是回退时记录）
        itinerary.unshift(from);
    }
    dfs("JFK"); // 起点永远是 JFK
    return itinerary;
}

Hierholzer 算法依赖“不断从当前节点出发，走完一条尽可能长的路径直到无法继续”，并将走过的节点按回溯顺序压入栈中，最终将所有路径拼接成一条欧拉路径。

接下来说明：为何这种看似“贪心 + 回溯”的策略是正确的，并适用于欧拉路径与回路。

性质一：栈中倒序恰好是欧拉路径的顺序

Hierholzer 算法的核心是：在无法再扩展路径（即遇末端节点）时将当前节点压入栈中，这等价于路径的“反向记录”。

对于欧拉路径

• 若图存在欧拉路径，则起点 s 出度比入度多 1，终点 t 入度比出度多 1。
• DFS 从 s 出发，最终会“遇末端”在 t —— 即第一次无法继续扩展的节点。
• 此时 t 被最早压入栈中，随着后续 DFS 回溯，s 最后入栈。
• 所以最终栈中为 t → … → s，倒序后得到 s → … → t，即完整的欧拉路径。

对于欧拉回路

• 欧拉回路所有节点入度 = 出度，路径终点应与起点一致。
• 从起点 s 出发，DFS 遍历所有边，最终回到 s，此时 s 是最后回溯入栈的节点。
• 所以栈中为 s → … → s，倒序后仍得到完整的回路路径。

小结

无论是欧拉路径还是回路，DFS 终止节点最早入栈，起点最晚入栈， 因此栈倒序即为正向路径。

性质二：“遇末端压栈”是反向路径构造的关键

每次 DFS 尽量深入，直到某节点无未访问的出边，称之为“当前末端节点”：

• 若首次遇末端的是全局终点 t，自然作为路径终点；
• 若是路径中的中继节点，说明它所有出边都已被走完（“被清空”），此时压入栈中表示这一段路径已完成。

这种构造方式具备如下特征：

当前遇末端的节点，总是当前剩余图中某一条子路径的“终点”。 在将其压入栈中后，相当于“剪掉”这段子路径。

之后如果从主路径上其他节点重新开始 DFS， 会构造新的子路径，并拼接到先前路径中。

因此，“遇末端压栈”其实是不断将路径段按回溯顺序压入结果栈的过程， 最终反转即得完整路径。

性质三：拼接子路径等价于延伸覆盖所有边

Hierholzer 算法通过主路径与子路径的拼接，实现对所有边的覆盖。

举例来说，设第一次 DFS 构建出主路径 A → B → C → D，但 B 节点仍有未访问的回路 B → E → F → B。此时：

• 算法沿主路径回溯，将 D 和 C 压入栈；
• 回溯至 B 时，发现其仍有出边，于是开始新一轮 DFS，从 B → E → F → B；
• 再次回到 B 时，出边已清空，开始回溯并将 B、F、E、B 入栈；
• 最后主路径起点 A 入栈。

此时栈中为 D, C, B, F, E, B, A，反转后得到完整欧拉路径：

A → B → E → F → B → C → D

这种拼接操作，实际上等价于在主路径上发现新回路时，将其原地插入主路径中。

由于每条边都只访问一次，且 DFS 时就被删除，整个过程保证不重不漏，构造出完整欧拉路径。

欧拉路径 vs 欧拉回路：算法是否都有效？

是的，Hierholzer 算法同样适用于欧拉路径和欧拉回路，差别仅在起点选择与终点处理方式。

类型	起点选择	路径终止位置	DFS 首次遇末端	栈顺序
欧拉路径	out(s) = in(s)+1	终点 t	最早入栈	t ... s
欧拉回路	任一非孤立点	回到起点	起点最后入栈	s ... s

因此，无需区分处理流程，只需正确选择起点即可通用。

附录：为何 Hierholzer 算法高效？

相比暴力回溯，Hierholzer 算法不仅更快，而且更结构化。以 “LeetCode 332. 重新安排行程” 为例，其高效性来源于以下几点：

1. 避免无效回溯树枝

暴力回溯枚举所有可能路径，会产生许多“失效树枝”，例如提前走到终点导致图剩余部分不可达。而 Hierholzer 只要图满足欧拉条件，就从起点不断延展，遇末端就收集路径，避免了枚举与试错。

2. 反向收集，不做猜测

Hierholzer 不会预先构造路径，而是通过“走到底、再回溯”的方式按序收集节点，这种反向构造避免了状态回滚，天然符合栈式操作逻辑。

3. 利用结构性假设：有解就唯一覆盖

欧拉图有解意味着存在一条覆盖所有边的路径或回路，Hierholzer 算法正是以此为前提， 一步步剪掉路径段，最后组合为全局解，无需重复判断。

4. 时间复杂度为 O(E)

每条边最多访问和删除一次，每个节点最多压入栈一次，整体运行在线性时间内。

因此，Hierholzer 算法是典型的“结构特化”算法：它不追求普适性，而是深度利用欧拉图的特性，从而实现常规回溯难以匹敌的效率。

---

将 n 个皇后放置在 n×n 的棋盘上，使皇后彼此之间不能攻击（任意两个皇后不能处于同一行、同一列或同一对角线上）。
返回所有可能的解决方案。

LeetCode51. N 皇后

const backtrack = (row) => {
    if (row === n) {
        // 已放置完 n 个皇后，构造解
        res.push(path.map(col => '.'.repeat(col) + 'Q' + '.'.repeat(n - col - 1)));
        return;
    }

    for (let col = 0; col < n; col++) {
        if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) continue;

        // 放置皇后
        path.push(col);
        cols.add(col);
        diag1.add(row - col);
        diag2.add(row + col);
        // ...
    //...
//...

---

编写一个程序，通过填充空格来解决给定的数独问题。
数独的解法需满足：

• 数字 1-9 在每一行只能出现一次。
• 数字 1-9 在每一列只能出现一次。
• 数字 1-9 在每一个 3×3 宫格内只能出现一次。

LeetCode37. 解数独

var solveSudoku = function (board) {
    const rows = new Array(9).fill(0);
    const cols = new Array(9).fill(0);
    const blocks = Array.from({ length: 3 }, () => new Array(3).fill(0));
    const blanks = [];
    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            const num = Number(board[i][j]);
            if (num) {
                const mask = 1 << (num - 1);
                rows[i] |= mask;
                cols[j] |= mask;
                blocks[~~(i / 3)][~~(j / 3)] |= mask;
            } else {
                blanks.push([i, j]);
            }
        }
    }
    const dfs = (k) => {
        if (k === blanks.length) return true;
        const [i, j] = blanks[k];
        const bi = ~~(i / 3), bj = ~~(j / 3);
        const used = rows[i] | cols[j] | blocks[bi][bj];
        for (let x = 1; x <= 9; x++) {
            const mask = 1 << (x - 1);
            if (used & mask) continue;
            board[i][j] = `${x}`;
            rows[i] |= mask;
            cols[j] |= mask;
            blocks[bi][bj] |= mask;
            if (dfs(k + 1)) return true;
            board[i][j] = ".";
            rows[i] ^= mask;
            cols[j] ^= mask;
            blocks[bi][bj] ^= mask;
        }
        return false;
    };
    dfs(0);
};

总结：回溯算法

回溯是递归的副产品，只要有递归就会有回溯，所以回溯法也经常和二叉树遍历，深度优先搜索混在一起，因为这两种方式都是用了递归。

优化回溯算法只有剪枝一种方法。

回溯经典题型复杂度分析

子集问题分析:

• 时间复杂度：O(2ⁿ) 每个元素有“取”与“不取”两种状态，组合总数为 2ⁿ。

• 空间复杂度：O(n) 递归深度为 n，栈空间为 O(n)，每层额外开销为常数级。

排列问题分析:

• 时间复杂度：O(n!) 每一层有 n 个分支，下一层为 n-1，依此类推，共 n! 种排列。

• 空间复杂度：O(n) 递归深度为 n，系统栈使用 O(n) 空间。

组合问题分析:

• 时间复杂度：O(2ⁿ) 属于子集问题的变形，最坏情况下为 2ⁿ。

• 空间复杂度：O(n) 递归深度为 n，其他开销为常数级。

N 皇后问题分析:

• 时间复杂度：O(n!) 表面上看是 O(nⁿ)，但因剪枝优化，最坏情况下为 n!。

• 空间复杂度：O(n) 递归深度为 n，仅需记录当前皇后摆放状态。

解数独问题分析:

• 时间复杂度：O(9^m) m 是空格（’.’）的数量，每个位置最多尝试 9 种数字。

• 空间复杂度：O(n²) 最多递归 n² 层（即 81），每次调用只处理一个空格。