目录
递归/回溯
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 <= 4
digits[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 <= 30
2 <= candidates[i] <= 40
candidates
的所有元素 互不相同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] <= 10
nums
中的所有整数 互不相同
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] <= 10
nums
中的所有元素 互不相同
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; // 返回结果
}
};