衔接上篇（ ^ _ ^ ）
剪枝优化是回溯算法中一种重要的优化手段，其核心思想是 提前终止无效的递归分支，避免无意义的搜索，从而大幅减少计算量。通过合理剪枝，可以将指数级的时间复杂度降低到更优的水平。
一、剪枝的核心思想
在递归遍历决策树时，提前判断当前路径是否可能得到有效解：
- 若 不可能得到解 → 直接终止当前分支的递归（“剪掉”这个分支）
- 若 可能得到解 → 继续递归探索
二、剪枝的常见类型及示例
1. 可行性剪枝
在每一步判断当前路径是否满足问题的约束条件，若不满足则提前返回。
示例：组合总和问题
void backtrack(vector<int>& nums, int remain, int start, vector<int>& path, vector<vector<int>>& res) {if (remain < 0) return; // ✂️剪枝：剩余值为负数时直接返回if (remain == 0) {res.push_back(path);return;}for (int i = start; i < nums.size(); ++i) {if (nums[i] > remain) break; // ✂️剪枝：已排序，后续元素更大，无需尝试path.push_back(nums[i]);backtrack(nums, remain - nums[i], i, path, res);path.pop_back();}
}
关键点：
- 先对数组排序（
sort），使后续元素递增 - 当
nums[i] > remain时，后续元素必然更大，不可能满足条件 → 直接break
2. 重复性剪枝
避免生成重复的解（常见于元素有重复值的问题）。
示例：全排列II（含重复元素）
void backtrack(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& res) {if (path.size() == nums.size()) {res.push_back(path);return;}for (int i = 0; i < nums.size(); ++i) {// ✂️剪枝条件1：跳过已使用的元素if (used[i]) continue; // ✂️剪枝条件2：跳过重复元素（需先排序）if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;used[i] = true;path.push_back(nums[i]);backtrack(nums, used, path, res);path.pop_back();used[i] = false;}
}
关键点：
- 先对数组排序（
sort），使相同元素相邻 - 当
nums[i] == nums[i-1]且!used[i-1]时，说明前一个相同元素未被使用 → 当前分支会产生重复解 → 跳过
3. 对称性剪枝
利用问题本身的对称性，避免重复搜索对称解。
示例：生成回文数
在生成回文数时，只需构造前半部分，后半部分对称生成即可。
三、剪枝的实现技巧
| 技巧 | 适用场景 | 示例 |
|---|---|---|
| 排序 + 提前终止循环 | 组合问题、子集问题 | if (nums[i] > remain) break |
索引标记（start） | 避免重复选择元素 | 组合问题中的 for (i = start) |
| 哈希表记录已访问状态 | 棋盘类问题（如数独） | 记录某行/列/宫是否包含某数字 |
| 数学性质推导 | 利用数学公式提前排除不可能的情况 | N皇后问题的斜线检查 |
四、剪枝的意义
- 时间复杂度优化：将指数级复杂度降低到更优水平（例如从 O(n!) 优化到 O(n×n!)）
- 空间优化：减少递归深度和内存占用
- 实际效率提升：对于大规模输入，剪枝可能将不可行的问题变为可解
五、经典剪枝练习
- 组合总和II（不可重复选相同元素）：
if (i > start && nums[i] == nums[i-1]) continue - 子集II（含重复元素）：
if (i > start && nums[i] == nums[i-1]) continue - 数独求解：预先记录每行/列/宫已使用的数字，快速判断是否可填
