回溯算法

回溯模板与思路

回溯 = 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 皇后的列/对角线占用集合）

时间复杂度概览

start vs used[] 对比

回溯中最容易混淆的问题：何时用 start 下标，何时用 used[] 数组？答案取决于结果集是否关心顺序。

组合 / 子集 — 不关心顺序

{1,2,3} 和 {3,2,1} 是同一个子集。只需从 start 往后选，自然保证每种元素组合只出现一次，无需 used[]。

排列 — 关心顺序

{1,2,3} 和 {3,2,1} 是不同排列。每步可选任意未使用元素，用 used[] 记录当前路径已包含哪些下标。

对比一览

全排列

全排列：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。

字符串分割（回文划分）

从 start 枚举 end，若 s[start..end] 是回文则递归处理 end+1——与子集模板完全相同的 start 下标结构。

// LC 131 — Palindrome Partitioning (count all ways)
int countPalinPartitions(const string& s) {
    int n = s.size(), cnt = 0;
    auto isPalin = [&](int l, int r) {
        while (l < r) if (s[l++] != s[r--]) return false;
        return true;
    };
    function<void(int)> bt = [&](int start) {
        if (start == n) { cnt++; return; }
        for (int end = start; end < n; end++)
            if (isPalin(start, end))
                bt(end + 1);
    };
    bt(0);
    return cnt;
}

去重技巧

输入含重复元素时，不去重会产生相同结果集。去重的前提是先对数组排序，让相同元素相邻，然后在同一层跳过已经考虑过的相同值。

前提：先排序

sort(nums.begin(), nums.end()); — 让相同元素相邻，才能用相邻比较检测重复。

组合去重：i > start && nums[i] == nums[i-1]

// Combination dedup — sort first, skip same-valued siblings at same level
for (int i = start; i < (int)nums.size(); i++) {
    if (i > start && nums[i] == nums[i-1]) continue; // skip same-level duplicate
    path.push_back(nums[i]);
    comb(i + 1, nums, path, res);
    path.pop_back();
}

i > start 表示不是当前层第一个选择（第一个需要枚举），nums[i] == nums[i-1] 表示与左侧兄弟值相同——跳过，避免在同一层产生相同分支。

排列去重：i > 0 && nums[i] == nums[i-1] && !used[i-1]

// Permutation dedup — sort first, skip when prev sibling was backtracked
for (int i = 0; i < n; i++) {
    if (used[i]) continue;
    // !used[i-1]: prev element was a sibling (same level, already tried) → skip
    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;
}

used[i-1] == true 表示 nums[i-1] 是当前路径的祖先节点（不同层），此时 nums[i] 可以选；!used[i-1] 表示 nums[i-1] 刚刚回溯（同层兄弟），值与 nums[i] 相同，跳过以避免重复排列。

剪枝详解

剪枝 = 提前返回或跳过，减少无效搜索分支。以下是四种常见剪枝场景。

// Combination Sum pruning — requires pre-sorted candidates
for (int i = start; i < (int)candidates.size(); i++) {
    if (candidates[i] > remain) break; // larger elements can't help either → cut branch
    path.push_back(candidates[i]);
    bt(i, remain - candidates[i]); // i: reuse allowed
    path.pop_back();
}

棋盘问题

棋盘问题（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 数组快速判断冲突。

数独求解（LC 37）

遍历空格，对每个 '.' 尝试 '1'-'9'，用行/列/宫约束剪枝；失败则回溯将格子置回 '.'。

// LC 37 — Sudoku Solver
bool isValidCell(vector<vector<char>>& b, int r, int c, char d) {
    for (int i = 0; i < 9; i++) {
        if (b[r][i] == d || b[i][c] == d) return false;
        if (b[3*(r/3)+i/3][3*(c/3)+i%3] == d) return false;
    }
    return true;
}
bool solveSudoku(vector<vector<char>>& b) {
    for (int i = 0; i < 9; i++)
        for (int j = 0; j < 9; j++)
            if (b[i][j] == '.') {
                for (char d = '1'; d <= '9'; d++) {
                    if (isValidCell(b, i, j, d)) {
                        b[i][j] = d;
                        if (solveSudoku(b)) return true;
                        b[i][j] = '.'; // backtrack
                    }
                }
                return false;
            }
    return true;
}