Leetcode回溯算法part2

93. 复原 IP 地址

整体思路（先不看代码）

题目要求：

给定一个只包含数字的字符串 s，返回所有可能的合法 IP 地址。

什么是“合法 IP”？

一个 IP 地址必须满足：

例如：

• "25525511135" → "255.255.11.135"、"255.255.111.35"

为什么这是回溯问题？

因为题目要求的是：

• 枚举所有可能的切割方式

• 并且每一种切割方式都要判断是否合法

👉 一看到：

“切割字符串 + 所有可能方案”

就要立刻想到：

回溯（切割问题）

把问题抽象成一棵树（核心理解）

可以把问题理解为：

• 在字符串中 放 3 个点

• 把字符串切成 4 段

例如："25525511135"

第一刀 第二刀 第三刀
↓ ↓ ↓
255 | 255 | 11 | 135

树的含义

👉 当 已经放了 3 个点，剩下的那一段必须一次性判断是否合法。

整体解法拆解（两部分）

✅ 第一部分：合法性判断（isValid）

这是本题的**“规则引擎”**，负责判断：

s[start..end] 能不能作为一个 IP 段

✅ 第二部分：回溯切割字符串

• 用回溯尝试在不同位置插入 .

• 每插入一次，就相当于确定了一段

• 插入 3 个点后，检查最后一段

class Solution {
public:

vector<string>result;

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<s.size();i++){
if(isValid(s,startIndex,i)){
s.insert(s.begin()+i+1,'.');
n++;
backtracking(s,n,i+2);
n–;
s.erase(s.begin()+i+1);
}
}
}

vector<string> 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<int>& 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<vector<int>>result;
vector<int>sub;

void backtracking(vector<int>&nums,int startIndex){
result.push_back(sub);
if(startIndex>=nums.size())return;
for(int i= startIndex;i<nums.size();i++){
sub.push_back(nums[i]);
backtracking(nums,i+1);
sub.pop_back();
}

}

vector<vector<int>> subsets(vector<int>& 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<int>& nums, int startIndex)

• startIndex：保证子序列顺序

• 不需要 target / sum

• 状态主要靠 path

✅ ② 收集结果的时机（非常重要）

if (path.size() > 1) { result.push_back(path); }

含义：

• 只要当前路径长度 ≥ 2

• 就是一个合法递增子序列

• 不需要等到叶子节点

👉 这一点和「子集问题」非常像

✅ ③ 单层搜索逻辑（核心）

• 从 startIndex 开始遍历

• 同时满足：

  • 递增条件

  • 同层去重条件

class Solution {
public:
vector<vector<int>>result;
vector<int>path;

void backtracking(vector<int>& nums,int startIndex){
if(path.size()>1){
result.push_back(path);
}
int set[201]={0};
for(int i = startIndex;i<nums.size();i++){
if ((!path.empty() && nums[i] < path.back())
|| set[nums[i] + 100] == 1) {
continue;
}
path.push_back(nums[i]);
set[nums[i] + 100] = 1;
backtracking(nums,i+1);
path.pop_back();
}
}

vector<vector<int>> findSubsequences(vector<int>& 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]

树结构含义

回溯三部曲（对应本题）

✅ ① 回溯函数参数

void backtracking(vector<int>& nums, vector<bool>& used)

为什么需要 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<vector<int>>result;
vector<int>path;
void backtracking(vector<int>&nums,vector<bool>&used){
if(path.size()==nums.size()){
result.push_back(path);
return;
}

for(int i = 0 ; i<nums.size();i++){
if(used[i]==true)continue;
used[i]=true;
path.push_back(nums[i]);
backtracking(nums,used);
used[i]=false;
path.pop_back();
}

}

vector<vector<int>> permute(vector<int>& nums) {
result.clear();
path.clear();
vector<bool>used(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<vector<int>> result;
vector<int> path;
void backtracking (vector<int>& nums, vector<bool>& 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<vector<int>> permuteUnique(vector<int>& nums) {
result.clear();
path.clear();
sort(nums.begin(), nums.end()); // 排序
vector<bool> 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<vector<string>> result;
bool isValid(int row,int col,vector<string>& chessboard,int n){
for(int i=0;i<row;i++){
if(chessboard[i][col]=='Q')return false;
}
for(int i = row-1,j=col-1;i>=0 && j>=0;i–,j–){
if(chessboard[i][j]=='Q')return false;
}
for(int i = row-1,j=col+1;i>=0 && j<n;i–,j++){
if(chessboard[i][j]=='Q')return false;
}
return true;
}
void backtracking(int n,int row,vector<string>&chessboard){
if(row == n){
result.push_back(chessboard);
return;
}

for(int col = 0; col<n;col++){
if(isValid(row,col,chessboard,n)){
chessboard[row][col]='Q';
backtracking(n,row+1,chessboard);
chessboard[row][col]='.';
}
}
}

vector<vector<string>> solveNQueens(int n) {
result.clear();
vector<string>chessboard(n,string(n,'.'));
backtracking(n,0,chessboard);
return result;
}
};

37. 解数独

整体思路（先不看代码）

题目要求：

给定一个 9×9 的数独棋盘（部分已填），填满整个棋盘，使其满足数独规则。

数独规则（三个约束）

对每个数字 '1'~'9'：

数独 = 棋盘回溯 + “找到一个解就停”

这是数独和 N 皇后最大的不同：

👉 所以数独的回溯函数 必须返回 bool 👉 一旦找到合法解，立刻停止搜索

整体回溯策略（非常关键）

核心思想一句话：

每次找一个空格 '.'，尝试填 1~9，能填就继续，填不下就回退

搜索顺序是这样的：

回溯函数 backtracking 详解

bool backtracking(vector<vector<char>>& board)

👉 返回值含义非常重要：

• 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] = '.';

这是数独回溯的灵魂三行：

发生了什么？

⑤ 为什么这里要 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<vector<char>>& 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; }

③ 检查 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 皇后（本质差异）

这是非常重要的对比：

class Solution {
public:
bool backtracking(vector<vector<char>>& board){
for(int i = 0;i<board.size();i++){
for(int j=0;j<board.size();j++){
if(board[i][j]=='.'){
for(char k='1';k<='9';k++){
if (isValid(i, j, k, board)) {
board[i][j] = k; // 放置k
if (backtracking(board)) return true; // 如果找到合适一组立刻返回
board[i][j] = '.'; // 回溯，撤销k
}
}
return false;
}
}
}
return true;
}

bool isValid(int row ,int col,char k,vector<vector<char>>&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<startrow + 3;i++){
for(int j=statrcol;j<statrcol+3;j++){
if(board[i][j]==k)return false;
}
}
return true;
}

void solveSudoku(vector<vector<char>>& board) {
backtracking(board);
}
};