【递归与回溯深度解析：经典题解精讲（上篇）】—— LeetCode
文章目录
- 全排列
- 子集
- 找出所有子集的异或总和再求和
- 全排列||
- 电话号码的字母组合
- 括号生成
全排列
解题思路
这是一道典型的 回溯（Backtracking）问题，我们需要枚举所有可能的子集。关键点是每个数字都有两种选择：要么包含，要么不包含。
详细步骤：
- 回溯的核心思想：
每个元素都有两种选择：加入当前子集或者不加入。
通过递归，处理完每个元素后生成对应的子集。 - 终止条件：
如果当前遍历的索引等于数组长度，说明已经生成一个完整的子集，将其加入结果。 - 回溯的过程：
将当前元素加入子集，继续递归。
回溯后，将当前元素移除，继续探索不加入当前元素的可能性
class Solution
{
// 存储最终结果的二维数组，每个子数组是一个排列
vector<vector<int>> ret;
// 当前递归路径，用于构建一个排列
vector<int> path;
// 标记数组，用于记录 nums 中的元素是否被使用过
bool check[7]; // 假设 nums.size() 最大为 7，实际可用动态数组优化
public:
vector<vector<int>> permute(vector<int>& nums)
{
// 开始深度优先搜索
dfs(nums);
return ret;
}
// 深度优先搜索函数
void dfs(vector<int>& nums)
{
// 如果当前路径的长度等于 nums 的大小，表示形成了一个完整排列
if(nums.size() == path.size())
{
// 将当前路径加入最终结果
ret.push_back(path);
return;
}
// 遍历 nums 中的每个元素
for(int i = 0; i < nums.size(); i++)
{
// 如果当前元素未被使用
if(!check[i])
{
// 将当前元素加入路径
path.push_back(nums[i]);
// 标记该元素为已使用
check[i] = true;
// 递归处理下一个位置
dfs(nums);
// 回溯：撤销选择
path.pop_back();
// 解除标记，表示该元素可以再次使用
check[i] = false;
}
}
}
};
子集
解题思路
这是一个典型的 回溯+交换（Backtracking with swapping）问题。关键点是枚举数组的所有排列组合。为了实现全排列，每次递归时需要将一个数字固定到当前位置，然后递归处理剩余数字。
详细步骤：
- 回溯的核心思想：
固定当前的一个数字，通过递归处理剩余数字。
通过交换，动态调整数组，避免额外空间开销。 - 终止条件：
如果当前索引达到数组长度，说明已经生成一个完整排列，将其加入结果。 - 回溯的过程：
将当前索引位置的数字与后续数字交换，递归处理剩余数字。
回溯时恢复数组原状（撤销交换）。
class Solution
{
// `ret` 用于存储所有子集的结果
vector<vector<int>> ret;
// `path` 用于存储当前递归路径上的子集
vector<int> path;
public:
// 主函数，用于计算输入数组的所有子集
vector<vector<int>> subsets(vector<int>& nums)
{
// 从第 0 个元素开始深度优先搜索
dfs(nums, 0);
// 返回最终生成的所有子集
return ret;
}
// 深度优先搜索函数，`nums` 为输入数组，`pos` 为当前元素的位置索引
void dfs(vector<int>& nums, int pos)
{
// 递归结束条件：如果已经遍历到数组末尾，将当前路径加入结果
if (nums.size() == pos)
{
ret.push_back(path); // 将当前路径（一个子集）添加到结果集中
return; // 终止当前递归
}
// 选择当前元素：将当前元素加入路径
path.push_back(nums[pos]);
// 递归处理包含当前元素的子集
dfs(nums, pos + 1);
// 回溯：移除最后加入的元素，恢复路径状态
path.pop_back();
// 不选择当前元素：直接递归处理不包含当前元素的子集
dfs(nums, pos + 1);
}
};
找出所有子集的异或总和再求和
解题思路
这是一道典型的 回溯 问题，要求计算所有子集的异或值总和。
子集枚举：通过回溯枚举所有子集。
异或计算：在回溯的过程中，用一个变量记录当前路径的异或值。
终止条件：当遍历到数组末尾时，将当前异或值累加到结果中。
详细步骤：
- 使用回溯生成所有子集，定义一个变量记录当前子集的异或总和。
在回溯时，每次有两种选择：
- 选择当前元素：更新异或值并递归。
不选择当前元素：保持当前状态递归。
遍历完后，将路径上的异或值加入结果中。
class Solution
{
// 用于记录当前路径中的 XOR 结果
int path;
// 用于记录所有子集的 XOR 结果的总和
int sum;
public:
int subsetXORSum(vector<int>& nums)
{
// 从 0 开始的深度优先搜索 (DFS)
dfs(nums, 0);
// 返回累加的 XOR 和
return sum;
}
// 深度优先搜索函数，用于生成所有子集并计算 XOR
void dfs(vector<int>& nums, int pos)
{
// 每次进入递归时，将当前路径的 XOR 结果加入总和
sum += path;
// 从当前位置开始，尝试添加下一个数字
for(int i = pos; i < nums.size(); i++)
{
// 将当前数字加入路径（通过 XOR 操作）
path ^= nums[i];
// 递归调用，处理当前位置之后的数字
dfs(nums, i + 1);
// 撤销选择，恢复路径到上一个状态
path ^= nums[i];
}
}
};
全排列||
解题思路
这是一道 回溯+剪枝 问题，核心在于生成全排列的同时避免重复。
关键点：
- 排序去重：
为了避免重复，先将数组排序。
在递归时，当遇到相同的元素且上一个相同的元素还未使用完时，跳过该分支。 - 状态数组：
使用一个 check数组记录当前元素是否被使用，防止重复选取。 - 回溯过程：
在路径中加入当前数字，递归处理剩余数字。
回溯时移除当前数字。
class Solution
{
vector<vector<int>> ret; // 用于存储所有不重复的排列结果
vector<int> path; // 当前排列的路径
bool check[9]; // 用于标记某个元素是否已被使用（假设输入数组最多有 9 个元素）
public:
vector<vector<int>> permuteUnique(vector<int>& nums)
{
// 对输入数组进行排序，这是为了处理重复元素，方便去重
sort(nums.begin(),nums.end());
dfs(nums, 0); // 从第 0 个位置开始深度优先搜索
return ret; // 返回所有不重复排列的结果
}
void dfs(vector<int>& nums, int pos)
{
// 如果路径的长度等于数组大小，说明找到一个完整的排列
if (pos == nums.size())
{
ret.push_back(path); // 将当前排列加入结果集
return; // 结束当前递归
}
// 遍历数组中的每个元素
for (int i = 0; i < nums.size(); i++)
{
// 如果当前元素未被使用
// 并且以下任一条件成立：
// 1. 当前是第一个元素 (i == 0)
// 2. 当前元素与前一个元素不同 (nums[i] != nums[i - 1])
// 3. 当前元素等于前一个元素，但前一个元素已被使用 (check[i - 1] == true)
if (check[i] == false && (i == 0 || nums[i] != nums[i - 1] || check[i - 1]))
{
path.push_back(nums[i]); // 将当前元素加入路径
check[i] = true; // 标记当前元素已被使用
dfs(nums, pos + 1); // 递归处理下一个位置
path.pop_back(); // 回溯：移除最后一个元素
check[i] = false; // 回溯：取消当前元素的使用标记
}
}
}
};
电话号码的字母组合
解题思路
这是一个 回溯问题，核心在于处理多分支递归。每个数字可以映射到多个字母，相当于在路径中枚举每个数字对应的字母。
详细步骤：
- 建立映射表：
使用哈希表记录数字到字母的映射关系。 - 回溯搜索：
每次递归处理一个数字，遍历其对应的所有字母。
将当前字母加入路径，递归处理剩余数字。
回溯时移除当前字母。 - 终止条件：
如果路径长度等于输入字符串长度，生成一个完整的字母组合。
class Solution
{
string path; // 用于存储当前的组合路径
vector<string> ret; // 存储所有可能的字母组合结果
string hash[10] = {"", "", // 映射 0 和 1 对应无字母
"abc", // 映射数字 2 到对应的字母
"def", // 映射数字 3
"ghi", // 映射数字 4
"jkl", // 映射数字 5
"mno", // 映射数字 6
"pqrs", // 映射数字 7
"tuv", // 映射数字 8
"wxyz"}; // 映射数字 9
public:
vector<string> letterCombinations(string digits)
{
// 如果输入的数字字符串为空，直接返回空的结果集
if(digits.size() == 0) return ret;
// 从第 0 个数字开始进行深度优先搜索 (DFS)
dfs(digits, 0);
// 返回所有可能的字母组合
return ret;
}
void dfs(string& digits, int pos)
{
// 如果当前的路径长度等于输入的数字长度，说明已生成一个完整的字母组合
if(pos == digits.size())
{
ret.push_back(path); // 将当前路径加入结果集
return; // 结束当前递归
}
// 遍历当前数字对应的所有字母
for(auto ch : hash[digits[pos] - '0'])
{
path.push_back(ch); // 将当前字母加入路径
dfs(digits, pos + 1); // 递归处理下一个数字
path.pop_back(); // 回溯：移除最后一个字母
}
}
};
括号生成
解题思路
这是一个 回溯问题，关键在于如何保证括号的合法性。
详细步骤：
- 规则约束：
只有在左括号数量未超过 n 时，才可以加入左括号。
只有在右括号数量小于左括号数量时，才可以加入右括号。 - 递归过程：
每次递归处理一个括号，根据约束条件选择加入左括号或右括号。 - 终止条件：
当左右括号数量都等于 n 时，生成一个完整的括号组合。
class Solution
{
int left, right, n; // `left`表示当前已经使用的左括号数量，`right`表示已使用的右括号数量，`n`表示总的括号对数
vector<string> ret; // 存储所有可能的合法括号组合结果
string path; // 当前生成的括号路径
public:
vector<string> generateParenthesis(int _n)
{
n = _n; // 初始化括号对数
dfs(); // 开始深度优先搜索
return ret; // 返回所有合法的括号组合
}
void dfs()
{
// 如果右括号数量等于括号对数，说明当前路径是一个完整的合法括号组合
if(right == n)
{
ret.push_back(path); // 将当前路径加入结果集
return; // 结束当前递归
}
// 如果左括号数量小于总括号对数，可以继续添加左括号
if(left < n)
{
path.push_back('('); // 添加一个左括号
left++; // 左括号计数加一
dfs(); // 递归处理下一个状态
path.pop_back(); // 回溯：移除最后一个括号
left--; // 回溯：左括号计数减一
}
// 如果右括号数量小于左括号数量，可以继续添加右括号
if(right < left)
{
path.push_back(')'); // 添加一个右括号
right++; // 右括号计数加一
dfs(); // 递归处理下一个状态
path.pop_back(); // 回溯：移除最后一个括号
right--; // 回溯：右括号计数减一
}
}
};