回溯算法

回溯模板与思路

回溯 = DFS + 撤销。三步：选择（make）→ 递归（recurse）→ 撤销（undo）。关键是明确：状态是什么、选择集合是什么、何时剪枝。

通用模板

// General backtracking template
void backtrack(State& state, Choices& choices) {
    if (isSolution(state)) {
        record(state);
        return;
    }
    for (auto& choice : choices) {
        if (isValid(state, choice)) {
            make(state, choice);          // choose
            backtrack(state, remaining);  // recurse
            undo(state, choice);          // unchoose
        }
    }
}

剪枝策略

• 排序后跳过相邻重复元素（去重）
• 当前路径已超出约束（长度、总和）立即返回
• 剩余元素不足以凑够目标数量时返回
• 对称剪枝（如 N 皇后的列/对角线占用集合）

时间复杂度概览

全排列

全排列：n 个元素的所有排列。用 used[] 布尔数组标记已选元素。含重复元素时先排序，相同元素只选第一个未使用的（跳过 used[i-1] == false && nums[i] == nums[i-1]）。

// LC 46 — All Permutations (no duplicates)
vector<vector<int>> permute(vector<int>& nums) {
    int n = nums.size();
    vector<bool> used(n, false);
    vector<int> path;
    vector<vector<int>> res;
    function<void()> bt = [&]() {
        if ((int)path.size() == n) { res.push_back(path); return; }
        for (int i = 0; i < n; i++) {
            if (used[i]) continue;
            used[i] = true; path.push_back(nums[i]);
            bt();
            path.pop_back(); used[i] = false;
        }
    };
    bt();
    return res;
}

// LC 47 — Permutations II (with duplicates)
vector<vector<int>> permuteUnique(vector<int>& nums) {
    sort(nums.begin(), nums.end()); // sort to group duplicates
    int n = nums.size();
    vector<bool> used(n, false);
    vector<int> path;
    vector<vector<int>> res;
    function<void()> bt = [&]() {
        if ((int)path.size() == n) { res.push_back(path); return; }
        for (int i = 0; i < n; i++) {
            if (used[i]) continue;
            // skip duplicate: same value, prev sibling not yet tried
            if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
            used[i] = true; path.push_back(nums[i]);
            bt();
            path.pop_back(); used[i] = false;
        }
    };
    bt();
    return res;
}

典型题目

• 46. 全排列（无重复）
• 47. 全排列 II（含重复元素）
• 60. 排列序列（第 k 个排列，数学直接求更优）

交换法：另一种实现：将位置 i 的元素与后续所有元素交换，递归处理 i+1 以后，交换回来。省去 used[] 但不易去重。

组合 & 子集

用 start 参数控制下一次选择的起始下标，避免重复（保证选择单调递增）。含重复元素时先排序，跳过 i > start && candidates[i] == candidates[i-1] 的情况。

// LC 78 — Subsets (all subsets of distinct elements)
vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> res;
    vector<int> path;
    function<void(int)> bt = [&](int start) {
        res.push_back(path); // record at every node, not just leaves
        for (int i = start; i < (int)nums.size(); i++) {
            path.push_back(nums[i]);
            bt(i + 1);
            path.pop_back();
        }
    };
    bt(0);
    return res;
}

// LC 39 — Combination Sum (elements reusable)
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    sort(candidates.begin(), candidates.end());
    vector<vector<int>> res;
    vector<int> path;
    function<void(int, int)> bt = [&](int start, int remain) {
        if (remain == 0) { res.push_back(path); return; }
        for (int i = start; i < (int)candidates.size(); i++) {
            if (candidates[i] > remain) break; // pruning
            path.push_back(candidates[i]);
            bt(i, remain - candidates[i]); // i not i+1 (reuse allowed)
            path.pop_back();
        }
    };
    bt(0, target);
    return res;
}

典型题目

• 78. 子集（每个元素选/不选）
• 90. 子集 II（含重复元素）
• 39. 组合总和（元素可重复使用）
• 40. 组合总和 II（每个元素只用一次）
• 131. 分割回文串（字符串分割）

可重用 vs 不可重用：元素可重复使用时，递归传入 start = i（不前进）；不可重用时传入 start = i + 1。

棋盘问题

棋盘问题（N 皇后、数独）的状态是格子的当前填充，选择集合是当前行/格可合法放置的值，约束是行/列/对角线/九宫格的唯一性。

// LC 51 — N-Queens
vector<vector<string>> solveNQueens(int n) {
    vector<bool> col(n), diag1(2*n), diag2(2*n);
    vector<string> board(n, string(n, '.'));
    vector<vector<string>> res;
    function<void(int)> bt = [&](int row) {
        if (row == n) { res.push_back(board); return; }
        for (int c = 0; c < n; c++) {
            if (col[c] || diag1[row-c+n] || diag2[row+c]) continue;
            col[c] = diag1[row-c+n] = diag2[row+c] = true;
            board[row][c] = 'Q';
            bt(row + 1);
            board[row][c] = '.';
            col[c] = diag1[row-c+n] = diag2[row+c] = false;
        }
    };
    bt(0);
    return res;
}

典型题目

• 51. N 皇后（输出所有合法棋盘布局）
• 52. N 皇后 II（只计数量）
• 37. 解数独（填满所有空格）

对角线标记：N 皇后中，主对角线用 row-col+n 索引，副对角线用 row+col 索引，各自一个 bool 数组快速判断冲突。