本文最后更新于：2025年11月29日下午

🧠 递归与回溯 · 思考题与练习详解

“回溯的本质不是暴力，而是把暴力拆解成一棵可控、有序、可剪枝的搜索树。”

在第七周「递归与回溯」中，我们建立了统一的回溯三段式框架，并从排列、组合、子集与 N 皇后等经典场景切入，理解了“选择 → 递归 → 撤销选择”的搜索过程。

本篇我们将针对上一周列出的思考题进行深度剖析，并附带 C++ 示例代码，让你完全吃透回溯思想。

🧩 思考题一

为什么子集问题中，所有节点都是答案，而排列问题只有叶子节点是答案？

💡 解析

子集（Subsets）问题的目标是：

求所有可能的子集（包括空集）

例如：输入 [1,2,3]，输出包括：

1	`[], [1], [2], [1,2], [1,2,3] ...`

在回溯树中，每个节点对应的是「当前已选择的集合」：

          []
      /     |     \
    [1]    [2]    [3]
   /  \      ...
[1,2] [1,3]

🧠 只要走到一个节点，它本质上就是一个合法子集。 因此：

子集问题的 每个节点都是答案
所以我们在递归开始就 push_back(path)

相比之下，排列（Permutation） 的目标是：

生成所有长度为 n 的排列

例如 [1,2,3] 必须产生长度为 3 的结果。

在回溯树中：

       []
  /      |       \
[1]     [2]     [3]
 ...      ...     ...

只有到达 深度等于 n 的叶子节点 才形成一个完整排列：

[1,2,3]
[2,3,1]
[3,1,2]
…

✔ 结论

问题类型	什么是“合法解”？	何时收集答案？
子集	任意路径都是一个子集	遍历到任意节点
排列	必须长度等于 n	到达叶子节点

回溯的本质差异来自“什么算是解”。

🧩 思考题二

请用回溯解决以下问题：

A. 电话号码字母组合（LeetCode #17）

📌 题目简述

输入：“23”

输出：

1	`["ad","ae","af","bd","be","bf","cd","ce","cf"]`

🧠 解法核心

digits 每一位对应一个字符集合（如 2 → “abc”）
每一位选一个字符 → DFS 组合所有可能路径

💻 C++ 解法

class Solution {
public:
    vector<string> res;
    string path;
    vector<string> mp = {
        "", "", "abc", "def", "ghi",
        "jkl", "mno", "pqrs", "tuv", "wxyz"
    };

    void backtrack(const string& digits, int idx) {
        if (idx == digits.size()) {
            res.push_back(path);
            return;
        }
        int d = digits[idx] - '0';
        for (char c : mp[d]) {
            path.push_back(c);
            backtrack(digits, idx + 1);
            path.pop_back();
        }
    }

    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        backtrack(digits, 0);
        return res;
    }
};

B. 分割回文串（LeetCode #131）

📌 核心思想

每次切一段 substring
若该段是回文 → 递归剩余部分
否则跳过（剪枝）

💻 C++ 实现

class Solution {
public:
    vector<vector<string>> res;
    vector<string> path;

    bool isPal(const string& s, int l, int r) {
        while (l < r) if (s[l++] != s[r--]) return false;
        return true;
    }

    void backtrack(const string& s, int start) {
        if (start == s.size()) {
            res.push_back(path);
            return;
        }

        for (int end = start; end < s.size(); end++) {
            if (!isPal(s, start, end)) continue;

            path.push_back(s.substr(start, end - start + 1));
            backtrack(s, end + 1);
            path.pop_back();
        }
    }

    vector<vector<string>> partition(string s) {
        backtrack(s, 0);
        return res;
    }
};

C. 全排列 II（含重复数字，LeetCode #47）

📌 难点：如何去重？

先排序
同层相同数字必须跳过（经典技巧）

💻 C++ 解法

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<bool> used;

    void backtrack(vector<int>& nums) {
        if (path.size() == nums.size()) {
            res.push_back(path);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            if (used[i]) continue;

            // 去重关键：同一层不能选择两个相同的数
            if (i > 0 && nums[i] == nums[i-1] && !used[i-1])
                continue;

            used[i] = true;
            path.push_back(nums[i]);

            backtrack(nums);

            used[i] = false;
            path.pop_back();
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        used.assign(nums.size(), false);
        backtrack(nums);
        return res;
    }
};

🧩 思考题三

为什么 N 皇后可以用 O(1) 判断位置是否冲突？

💡 核心原因：三条规则

放置皇后 Q(row, col) 会影响三条方向：

同列冲突： col[col] == true
主对角线（左上 ↘ 右下）冲突： row + col 固定 → diag1[row + col]
副对角线（右上 ↙ 左下）冲突： row - col 固定为避免负数，偏移 + (n-1) → diag2[row - col + n - 1]

✔ 这些数组都能 O(1) 查冲突

因此放皇后只需：

1	`if (col[c] \|\| diag1[r+c] \|\| diag2[r-c+n-1]) skip;`

无须遍历棋盘，大幅降低搜索树规模。这也是 N 皇后回溯能跑得动的根本原因。

🧩 思考题四（进阶）

设计一个回溯算法，找出棋盘上所有可能的“骑士巡逻路径”（Knight’s Tour）

骑士巡逻问题是经典 NP 问题之一。

🧠 解法框架

从 (0,0) 出发
DFS 尝试所有 8 个方向
标记已访问
若走满 n² 尽为一个完整巡逻路径

💻 伪代码（简化）

bool backtrack(int r, int c, int step) {
    if (step == n*n) return true;

    for (auto [dr, dc] : knightMoves) {
        int nr = r + dr, nc = c + dc;
        if (合法且未访问) {
            visited[nr][nc] = true;
            if (backtrack(nr, nc, step + 1)) return true;
            visited[nr][nc] = false;
        }
    }
    return false;
}

⭐ 关键补充：

此题由于搜索空间巨大，往往要加入 Warnsdorff heuristic（启发式减少分支数）
属于“剪枝 + DFS”的典型高级回溯问题

✨ 总结

第七周的思考题重点强化以下回溯概念：

知识点	关键理解
子集 vs 排列	何时节点是答案？
去重技巧	排序 + used + 同层剪枝
快速合法性判断	O(1) 记忆化结构（N 皇后）
回溯模板	做选择 → 递归 → 撤销选择
启发式回溯	用于 Knight’s Tour、数独等高级问题