目录
递归/回溯
1. 17. 电话号码的字母组合
2. 22. 括号生成
3. 39. 组合总和
4. 46. 全排列
5. 78. 子集
递归/回溯
1. 17. 电话号码的字母组合
中等
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = "" 输出：[]
示例 3：
输入：digits = "2" 输出：["a","b","c"]
提示：
0 <= digits.length <= 4digits[i]是范围['2', '9']的一个数字。
// 定义一个类 Solution
class Solution {
public:
// 定义一个字符串向量 v，存储数字到字母的映射关系，数字 2 到 9 分别对应不同的字母组合
vector<string> v{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
// 定义一个字符串向量 result，用于存储所有可能的字母组合结果
vector<string> result;
// 定义一个字符串 path，用于记录当前组合的路径
string path;// 递归函数 recursive，用于生成所有可能的字母组合
void recursive(string digits, int index) {
// 递归结束条件：当 path 的长度等于输入的数字串长度时，将当前组合添加到结果中
if (path.size() == digits.size()) {
result.push_back(path);
return;
}// 根据当前数字获取对应的字母字符串
string s = v[digits[index] - '0'];// 遍历当前数字对应的每个字母
for (int i = 0; i < s.size(); ++i) {
// 将当前字母添加到 path
path.push_back(s[i]);// 递归调用，下一个数字
recursive(digits, index + 1);// 回溯：移除最后一个添加的字母，以便尝试下一个字母组合
path.pop_back();
}
}// 主函数 letterCombinations，调用递归函数并返回结果
vector<string> letterCombinations(string digits) {
// 如果输入为空，返回空的结果集
if (digits.size() == 0) return {};
// 调用递归函数，开始生成字母组合
recursive(digits, 0);// 返回所有生成的字母组合
return result;
}
};
2. 22. 括号生成
中等
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1 输出：["()"]
提示：
1 <= n <= 8
class Solution {
public:
vector<string> ans; // 存储所有有效的括号组合
string cur; // 当前构建的括号组合字符串
// 回溯函数
void backtrack(string& cur, int open, int close, int n) {
// 基线条件：当当前组合的长度等于 2*n 时，意味着已生成一个有效的括号组合
if (cur.size() == 2 * n) {
ans.push_back(cur); // 将当前组合添加到结果中
return; // 返回，结束当前递归
}
// 1. 尝试添加左括号
if (open < n) { // 只有在左括号数量小于 n 时才能添加左括号
cur.push_back('('); // 将左括号添加到当前组合
backtrack(cur, open + 1, close, n); // 递归调用，更新 open 数量
cur.pop_back(); // 回溯：移除最后一个字符，尝试其他组合
}
// 2. 尝试添加右括号
if (close < open) { // 只有在右括号数量小于左括号数量时才能添加右括号
cur.push_back(')'); // 将右括号添加到当前组合
backtrack(cur, open, close + 1, n); // 递归调用，更新 close 数量
cur.pop_back(); // 回溯：移除最后一个字符，尝试其他组合
}
}
// 生成 n 对括号的主函数
vector<string> generateParenthesis(int n) {
backtrack(cur, 0, 0, n); // 初始调用，open 和 close 都为 0
return ans; // 返回所有生成的有效括号组合
}
};
解释：
- 条件
if (close < open)确保右括号的数量不会超过左括号的数量，从而保持组合的有效性。
3. 39. 组合总和
中等
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：
输入：candidates = [2,3,6,7], target = 7 输出：[[2,2,3],[7]] 解释： 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。 7 也是一个候选， 7 = 7 。 仅有这两种组合。
示例 2：
输入: candidates = [2,3,5],target = 8 输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：
输入: candidates = [2], target = 1 输出: []
提示：
1 <= candidates.length <= 302 <= candidates[i] <= 40candidates的所有元素 互不相同1 <= target <= 40
class Solution {
public:
// 用于存储所有符合条件的组合
vector<vector<int>> result;
// 用于存储当前的组合路径
vector<int> path;// 递归+回溯函数
// candidates: 数组中的可选数字
// target: 目标和
// sum: 当前路径的和
// index: 当前选择开始的索引位置
void backTracking(vector<int>& candidates, int target, int sum, int index) {
// 如果当前和已经超过目标值，结束该路径
if(sum > target){
return;
}// 如果找到一个符合条件的组合
if(target == sum){
result.push_back(path); // 将当前路径加入结果集中
return;
}// 遍历候选数组，从 index 开始
for(int i = index; i < candidates.size(); ++i) {
// 将当前选择加入路径和 sum 中
sum += candidates[i];
path.push_back(candidates[i]);// 递归调用自身，传入i而不是index或index+1，以允许重复使用相同的元素
backTracking(candidates, target, sum, i);// 回溯，撤销当前选择
sum -= candidates[i];
path.pop_back();
}
}// 主函数，用于调用回溯函数并返回结果
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
backTracking(candidates, target, 0, 0); // 初始化 sum 为 0，从索引 0 开始
return result; // 返回符合条件的所有组合
}
};
解释：
关于for循环中int=index而不是i=0问题：
考虑一个具体的例子，假设我们有以下输入：
candidates = [2, 3, 6, 7] target = 7
1. 使用 index 控制
当 index 传入 0，第一次迭代将会是：
- 第一个元素
2（index = 0）- 选择
2，接下来可以再次选择2或选择3（因为i从0开始）。你将得到[2, 2, 3]这种组合。
- 选择
- 第二个元素
3（index = 1）- 当递归调用回来后，当前元素
2被弹出，index继续向前推进。 - 选择
3时，i从1开始，因此可以选择[3, 4]，形成组合[3, 4]。
- 当递归调用回来后，当前元素
这个方法避免了相同元素在同一层级的选择，比如 2 被重复选择。
2. 使用 0 开始的情况
如果 for 循环从 0 开始：
- 第一个元素
2（i = 0）- 选择
2，然后backTracking(candidates, target, sum, 0)再次递归调用，允许再次选择2。
- 选择
- 第二个元素
2再次选择（i = 0）- 你将得到路径
[2, 2, 2]，但也会通过选择2、然后2、然后3再生成组合。
- 你将得到路径
造成的后果
通过从 0 开始，每一层递归都允许选择之前已经被选中的元素，导致生成的组合可能重复。例如 [2, 2, 3] 和 [2, 3, 2] 被认为是不同的组合，但实际上它们是相同的组合。
总结
index变量的设计：允许算法在递归过程中控制哪些元素可以被选择，同时避免在同一递归层级重复选择已经在路径中的元素。- 从
0开始的后果：如果每次递归都从0开始，可能会产生重复组合，并增加计算的复杂度。
4. 46. 全排列
中等
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1] 输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1] 输出：[[1]]
提示：
1 <= nums.length <= 6-10 <= nums[i] <= 10nums中的所有整数 互不相同
class Solution {
public:
// 存储所有的排列结果
vector<vector<int>> result;
// 存储当前排列的路径
vector<int> path;// 回溯函数
void backTracking(vector<int>& nums, vector<bool>& used) {
// 终止条件：当前路径的长度等于数组的长度，表示形成了一个完整排列
if (nums.size() == path.size()) {
result.push_back(path); // 将当前排列加入结果集
return;
}// 遍历所有元素，尝试每种可能
for (int i = 0; i < nums.size(); ++i) {
// 如果该元素已经使用过，则跳过
if (used[i]) continue;// 标记当前元素为已使用
used[i] = true;
path.push_back(nums[i]); // 将元素加入当前排列路径
// 递归调用自身，继续生成排列
backTracking(nums, used);// 回溯，撤销当前选择，准备尝试其他排列
path.pop_back();
used[i] = false;
}
}// 主函数，返回所有的排列
vector<vector<int>> permute(vector<int>& nums) {
// 初始化标记数组，长度和 nums 一致，初始值为 false
vector<bool> used(nums.size(), false);
// 开始回溯
backTracking(nums, used);
return result;
}
};
5. 78. 子集
中等
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0] 输出：[[],[0]]
提示：
1 <= nums.length <= 10-10 <= nums[i] <= 10nums中的所有元素 互不相同
class Solution {
public:
vector<vector<int>> result; // 用于存储所有子集的结果
vector<int> path; // 当前的子集路径void backtrack(vector<int>& nums, int index) {
// 结束条件：当 index 等于数组大小时返回
if (index == nums.size()) {
return;
}// 将当前子集加入结果中
result.push_back(path);// 遍历剩余的元素，生成子集
for (int i = index; i < nums.size(); ++i) {
path.push_back(nums[i]); // 选择当前元素
backtrack(nums, i + 1); // 递归调用，选择下一个元素
path.pop_back(); // 回溯，撤销选择
}
}vector<vector<int>> subsets(vector<int>& nums) {
backtrack(nums, 0); // 从索引 0 开始
return result; // 返回结果
}
};
