Leetcode回溯算法part2
93. 复原 IP 地址
整体思路（先不看代码）
题目要求：
给定一个只包含数字的字符串
s，返回所有可能的合法 IP 地址。
什么是“合法 IP”？
一个 IP 地址必须满足：
-
由 4 段组成，用
.分隔 -
每一段：
-
数值在
0 ~ 255 -
不能有前导 0（除非就是
"0"）
-
例如：
-
"25525511135"→"255.255.11.135"、"255.255.111.35"
为什么这是回溯问题？
因为题目要求的是：
-
枚举所有可能的切割方式
-
并且每一种切割方式都要判断是否合法
👉 一看到：
“切割字符串 + 所有可能方案”
就要立刻想到：
回溯（切割问题）
把问题抽象成一棵树（核心理解）
可以把问题理解为：
-
在字符串中 放 3 个点
-
把字符串切成 4 段
例如："25525511135"
第一刀 第二刀 第三刀
↓ ↓ ↓
255 | 255 | 11 | 135
树的含义
| 回溯概念 | 本题含义 |
|---|---|
| 树的深度 | 已经放了几个点（n） |
| 每一层 | 决定当前这一段的结尾 |
| 每个节点 | 一个合法的 IP 段 |
| 一条路径 | 一个完整 IP 地址 |
👉 当 已经放了 3 个点，剩下的那一段必须一次性判断是否合法。
整体解法拆解（两部分）
✅ 第一部分：合法性判断（isValid）
这是本题的**“规则引擎”**，负责判断：
s[start..end]能不能作为一个 IP 段
✅ 第二部分：回溯切割字符串
-
用回溯尝试在不同位置插入
. -
每插入一次，就相当于确定了一段
-
插入 3 个点后，检查最后一段
class Solution {
public:
vectorresult;
bool isValid(const string&s,int start,int end){
if(start>end)return false;
if(s[start]=='0' && start != end){
return false;
}
int num = 0;
for(int i = start;i<=end;i++){
if(s[i]>'9'||s[i]<'0')return false;
num = num*10+(s[i]-'0');
if(num>255)return false;
}
return true;
}
void backtracking(string& s ,int n ,int startIndex){
if(n==3){
if(isValid(s,startIndex,s.size()-1)){
result.push_back(s);
}
return ;
}
for(int i = startIndex;i restoreIpAddresses(string s) {
result.clear();
if (s.size() < 4 || s.size() > 12) return result; // 算是剪枝了
backtracking(s, 0, 0);
return result;
}
}; 78. 子集
整体思路（先不看代码）
题目要求的是：
给定一个数组
nums，返回它的所有子集（幂集）。
例如：[1,2]
[] [1] [2] [1,2]
子集问题的最大特点
-
不要求固定长度
-
每个元素：选 or 不选
-
所有可能情况都要
👉 一句话判断：
“每个元素都有选 / 不选两种状态” → 子集问题 → 回溯
二、把子集问题抽象成一棵树（非常重要）
以 nums = [1,2,3] 为例：
[]
[1]
[2]
[1,2]
但在代码实现中，我们通常不显式写“选 / 不选”两条分支，而是用：
for 循环 + startIndex，自然枚举“选哪些”
三、子集 vs 组合（核心认知）
这是很多人第一次学子集时最容易混的点👇
组合问题（如 combine）
-
只有 path.size() == k 才收集结果
-
有明确“终止条件”
子集问题（本题）
每一个节点，都是一个合法子集
也就是说：
-
空集是子集
-
任何中间状态都是子集
-
不需要等到“叶子节点”
👉 这就是你代码里这句的真正含义：
result.push_back(sub);
四、回溯三部曲（对应本题）
✅ ① 回溯函数参数
void backtracking(vector& nums, int startIndex)
-
nums：原数组 -
startIndex：下一次可选择元素的起点
👉 startIndex 的作用依然是：
防止出现 [1,2] 和 [2,1] 这种重复子集
✅ ② 终止条件（子集的“特殊点”）
if (startIndex >= nums.size()) return;
这里的终止条件非常弱，原因是：
-
不靠终止条件收集结果
-
收集结果发生在“进入函数的第一行”
只要 startIndex 越界，就没法继续选了，直接返回即可。
✅ ③ 单层搜索逻辑
for (int i = startIndex; i < nums.size(); i++) {
sub.push_back(nums[i]);
backtracking(nums, i + 1);
sub.pop_back();
}
含义：
-
在当前层，从
startIndex开始 -
依次尝试把每个元素加入子集
-
然后递归向下扩展
class Solution {
public:
vector>result;
vectorsub;
void backtracking(vector&nums,int startIndex){
result.push_back(sub);
if(startIndex>=nums.size())return;
for(int i= startIndex;i> subsets(vector& nums) {
result.clear();
sub.clear();
backtracking(nums, 0);
return result;
}
}; 491. 非递减子序列
整体思路（先不看代码）
题目要求：
给定一个整数数组
nums，找出所有递增子序列（长度 ≥ 2），子序列不要求连续，但结果不能重复。
关键词拆解：
-
子序列：不要求连续 → 回溯
-
递增：有顺序约束
-
所有方案：不是求个数，是求列表
-
不能重复：这是难点
👉 一句话判断：
这是“子集类回溯 + 顺序约束 + 去重”的综合题
把问题抽象成一棵树（非常关键）
以 nums = [4,6,7,7] 为例：
[]
/ |
[4] [6] [7]
/ | |
[4,6] [4,7] [6,7] [7,7]
| |
[4,6,7] [4,7,7]
树结构里的限制
1️⃣ 不能下降
-
后选的数必须 ≥ 前一个数
2️⃣ 同一层不能选相同的数
-
否则会产生重复子序列
👉 难点不在“回溯”，而在**“同层去重”**
这道题的三大核心约束
✅ 1️⃣ 子序列 ≠ 子集
-
子集：元素选 or 不选
-
子序列：要保持原数组的相对顺序
所以：
-
只能从
startIndex往后选 -
不能回头
✅ 2️⃣ 递增约束（纵向约束）
nums[i] >= path.back()
如果当前数比路径最后一个小：
-
这条分支直接非法
-
必须剪掉
✅ 3️⃣ 去重约束（横向约束，最容易错）
同一层递归中，相同的数字只能用一次
否则会出现重复结果，比如：
[7]（选第一个 7） [7]（选第二个 7）
回溯三部曲（对应本题）
✅ ① 回溯函数参数
void backtracking(vector& nums, int startIndex)
-
startIndex：保证子序列顺序 -
不需要 target / sum
-
状态主要靠
path
✅ ② 收集结果的时机（非常重要）
if (path.size() > 1) { result.push_back(path); }
含义：
-
只要当前路径长度 ≥ 2
-
就是一个合法递增子序列
-
不需要等到叶子节点
👉 这一点和「子集问题」非常像
✅ ③ 单层搜索逻辑（核心）
-
从
startIndex开始遍历 -
同时满足：
-
递增条件
-
同层去重条件
-
class Solution {
public:
vector>result;
vectorpath;
void backtracking(vector& nums,int startIndex){
if(path.size()>1){
result.push_back(path);
}
int set[201]={0};
for(int i = startIndex;i> findSubsequences(vector& nums) {
result.clear();
path.clear();
backtracking(nums,0);
return result;
}
}; 46. 全排列
整体思路（先不看代码）
题目要求：
给定一个数组
nums，返回它的所有全排列。
例如：[1,2,3]
[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]
排列问题的“本质特征”
顺序敏感 ❗
这和前面的题有本质区别：
-
[1,2]和[2,1]是 两个不同解 -
每一个位置都要尝试所有还没用过的数
👉 一句话判断：
“顺序会产生不同结果” → 排列 → 一定要用 used 数组
把排列问题抽象成一棵树（非常关键）
以 nums = [1,2,3] 为例：
[]
/ |
[1] [2] [3]
/ / /
[1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
| | | | | |
[1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]
树结构含义
| 回溯概念 | 本题含义 |
|---|---|
| 树的深度 | path.size() |
| 每一层 | 决定“当前第几个位置放谁” |
| 每一层可选 | 所有还没用过的元素 |
| 叶子节点 | path.size() == nums.size() |
回溯三部曲（对应本题）
✅ ① 回溯函数参数
void backtracking(vector
为什么需要 used？
因为在排列中：
每个数字只能用一次，但每一层都要从 0 开始遍历
这和组合 / 子集 完全不同。
✅ ② 终止条件（什么时候收集结果）
if (path.size() == nums.size()) { result.push_back(path); }
含义：
-
当前路径长度等于数组长度
-
说明每个位置都已经放了一个数
-
得到一个完整排列
✅ ③ 单层搜索逻辑（排列的核心）
for (int i = 0; i < nums.size(); i++) {
注意这里：
-
不是从 startIndex
-
而是 每一层都从 0 开始
👉 因为排列的每一个位置，都可以放任何还没用过的数。
class Solution {
public:
vector>result;
vectorpath;
void backtracking(vector&nums,vector&used){
if(path.size()==nums.size()){
result.push_back(path);
return;
}
for(int i = 0 ; i> permute(vector& nums) {
result.clear();
path.clear();
vectorused(nums.size(),false);
backtracking(nums,used);
return result;
}
}; 47. 全排列 II
整体思路（先不看代码）
题目要求：
给定一个 可能包含重复数字 的数组
nums，返回所有 不重复的全排列。
例如：
nums = [1,1,2]
合法结果：
[1,1,2]
[1,2,1]
[2,1,1]
非法（重复）：
[1,1,2]（用第一个1）
[1,1,2]（用第二个1）
为什么“普通排列 + used[]”不够？
在 permute（无重复） 里：
if (used[i]) continue;
只能保证：
-
一个元素在一条排列里只用一次
❌ 但挡不住这种情况：
nums = [1,1,2]
第一层：
选 nums[0] = 1 → path = [1]
选 nums[1] = 1 → path = [1] （数值一样，但下标不同）
👉 下标不同，但值相同
👉 会生成一模一样的排列
所以：
排列去重 ≠ 防止重复使用元素
而是：
防止在同一层，用“相同的值”开头
排列去重的核心思想（一句话版）
相同的数字，必须“按顺序”使用
前一个没用，后一个不能用
这句话就是下面这行代码的数学含义：
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false)
if (
i > 0
&& nums[i] == nums[i - 1]
&& used[i - 1] == false
) {
continue;
}
翻译成一句人话：
如果当前数字和前一个数字相同，
且前一个数字在当前树枝中还没被用过，
那说明我正站在“同一层”，
这个分支一定会产生重复排列，必须跳过。
class Solution {
private:
vector> result;
vector path;
void backtracking (vector& nums, vector& used) {
// 此时说明找到了一组
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
// used[i - 1] == true，说明同一树枝nums[i - 1]使用过
// used[i - 1] == false，说明同一树层nums[i - 1]使用过
// 如果同一树层nums[i - 1]使用过则直接跳过
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
continue;
}
if (used[i] == false) {
used[i] = true;
path.push_back(nums[i]);
backtracking(nums, used);
path.pop_back();
used[i] = false;
}
}
}
public:
vector> permuteUnique(vector& nums) {
result.clear();
path.clear();
sort(nums.begin(), nums.end()); // 排序
vector used(nums.size(), false);
backtracking(nums, used);
return result;
}
}; 51. N 皇后
整体思路（先不看代码）
题目要求：
在一个
n × n的棋盘上，放置n个皇后，使得它们互不攻击，返回所有不同的摆放方案。
皇后的攻击规则
一个皇后会攻击：
-
同一列
-
左上 ↖ 右下 ↘ 对角线
-
右上 ↗ 左下 ↙ 对角线
👉 行不用检查，因为我们保证每一行只放一个皇后
N 皇后 = 典型“棋盘型回溯”
这类题的固定套路是：
一行一行放皇后，每一行选择一个合法的列
也就是说：
-
树的深度 = 行号
row -
每一层的选择 = 这一行皇后放在哪一列
col -
一个完整解 = 成功放完第
n行
把问题抽象成一棵树（关键理解）
以 n = 4 为例：
第 0 行：col = 0 / 1 / 2 / 3
↓
第 1 行：在合法列中选
↓
第 2 行：继续选
↓
第 3 行：继续选
↓
row == n → 得到一个解
👉 每一层只关心“这一行皇后能放在哪”
整体解法拆成两部分
✅ 第一部分：合法性判断 isValid
判断：
在
(row, col)放皇后，是否会和前面已经放的皇后冲突
⚠️ 只需要检查 row 之前的行
因为后面的行还没放。
✅ 第二部分：回溯放皇后
-
从第 0 行开始
-
每一行尝试所有列
-
放得下就递归到下一行
-
放不下就换列
-
行号到
n，收集结果
class Solution {
public:
vector> result;
bool isValid(int row,int col,vector& chessboard,int n){
for(int i=0;i=0 && j>=0;i--,j--){
if(chessboard[i][j]=='Q')return false;
}
for(int i = row-1,j=col+1;i>=0 && j&chessboard){
if(row == n){
result.push_back(chessboard);
return;
}
for(int col = 0; col> solveNQueens(int n) {
result.clear();
vectorchessboard(n,string(n,'.'));
backtracking(n,0,chessboard);
return result;
}
}; 37. 解数独
整体思路（先不看代码）
题目要求：
给定一个 9×9 的数独棋盘（部分已填），填满整个棋盘，使其满足数独规则。
数独规则（三个约束）
对每个数字 '1'~'9'：
-
同一行不能重复
-
同一列不能重复
-
同一个 3×3 宫格不能重复
数独 = 棋盘回溯 + “找到一个解就停”
这是数独和 N 皇后最大的不同：
| 题目 | 要不要所有解 |
|---|---|
| N 皇后 | 要所有方案 |
| 数独 | 只要一个解 |
👉 所以数独的回溯函数 必须返回 bool
👉 一旦找到合法解，立刻停止搜索
整体回溯策略（非常关键）
核心思想一句话：
每次找一个空格
'.'，尝试填1~9，能填就继续，填不下就回退
搜索顺序是这样的：
-
从左到右、从上到下扫描棋盘
-
找到第一个
'.' -
尝试填
'1'~'9' -
如果合法，递归填下一个空格
-
如果后面失败，撤销当前填写，换下一个数字
回溯函数 backtracking 详解
bool backtracking(vector
👉 返回值含义非常重要：
-
true：已经找到一个完整合法解 -
false：当前路径不行，需要回溯
① 找“当前要填的格子”
for (int i = 0; i < board.size(); i++)
{ for (int j = 0; j < board.size(); j++)
{ if (board[i][j] == '.') {
含义：
-
按顺序扫描棋盘
-
找到第一个空格
-
只处理这一个空格
⚠️ 注意：
一旦找到 '.'，后面的格子暂时不管
② 尝试填 '1' ~ '9'
for (char k = '1'; k <= '9'; k++) {
每一个 k，都是一个“选择”。
③ 合法性判断（剪枝）
if (isValid(i, j, k, board)) {
-
不合法 → 直接跳过
-
合法 → 尝试填入
④ 做选择 + 递归
board[i][j] = k; if (backtracking(board)) return true; board[i][j] = '.';
这是数独回溯的灵魂三行：
发生了什么？
-
尝试填 k
-
递归填后续空格
-
如果后面成功：
-
直接一路
return true -
整个搜索终止
-
-
如果后面失败：
-
回溯，撤销 k
-
尝试下一个数字
-
⑤ 为什么这里要 return false？
return false;
位置很关键，在这里：
if (board[i][j] == '.') { ... return false; }
含义是：
这个空格，1~9 全部试过了，都不行
那说明之前的某一步选错了，必须回溯
⑥ 什么时候返回 true？
return true;
在函数最后：
return true;
含义：
-
扫描完整个棋盘
-
没有找到任何 '.'
-
说明整个棋盘已经合法填满
-
找到一个解 ✔
五、合法性判断 isValid 逐段讲解
bool isValid(int row, int col, char k, vector
① 检查行
for (int i = 0; i < 9; i++) { if (board[row][i] == k) return false; }
② 检查列
for (int j = 0; j < 9; j++) { if (board[j][col] == k) return false; }
③ 检查 3×3 宫格
int startrow = (row / 3) * 3;
int startcol = (col / 3) * 3;
for (int i = startrow; i < startrow + 3; i++) {
for (int j = startcol; j < startcol + 3; j++) {
if (board[i][j] == k) return false;
}
}
👉 (row/3)*3 是定位宫格左上角的标准技巧
六、数独 vs N 皇后（本质差异）
这是非常重要的对比：
| 维度 | N 皇后 | 数独 |
|---|---|---|
| 搜索目标 | 所有解 | 任意一个解 |
| 回溯返回值 | void | bool |
| 搜索顺序 | 按行 | 按空格 |
| 剪枝依据 | 攻击规则 | 行 / 列 / 宫 |
| 找到解后 | 继续 | 立刻停止 |
class Solution {
public:
bool backtracking(vector>& board){
for(int i = 0;i>&board){
for(int i=0;i<9;i++){
if(board[row][i]==k)return false;
}
for(int j = 0;j<9;j++){
if(board[j][col]==k)return false;
}
int startrow = (row/3)*3;
int statrcol = (col/3)*3;
for(int i=startrow;i>& board) {
backtracking(board);
}
};
