LeetCode 热题100 之 回溯1
1.全排列
- 思路分析1（回溯）：要生成一个不含重复数字的数组 nums 的所有可能全排列，我们可以使用回溯算法。这种算法通过递归的方法探索所有可能的排列组合，并在合适的时机进行回溯，确保不会遗漏任何排列。
- 回溯算法
- 使用一个current数组来存储当前排列；
- 使用一个used布尔数组来标记哪些元素已经被加入到当前排列中；
- 当current的大小等于nums的大小时，说明我们已经形成了一个完整的排列，可以将其添加到结果result中；
- 递归与回溯
- 递归的每一层代表选择一个数字加入current，并探索这个数字下的所有可能。
- 一旦探索完成，我们需要“撤销”这个操作，即从current中移除该数字，并标记为未使用（回溯）；
具体实现代码（详解版):
class Solution {
public:
void backback(vector<int>& nums, vector<int>& current,
vector<vector<int>>& resut, vector<bool>& used) {
// 如果当前排列的大小等于nums的大小，说明形成了一个完整的排列
if (current.size() == nums.size()) {
resut.push_back(current); // 将当前排列加入到结果中
return; // 返回上一层
}
// 遍历所有数字
for (int i = 0; i < nums.size(); i++) {
// 如果nums[i]已经被使用，跳过该数字
if (used[i])
continue;
// 标记nums[i]为已使用
used[i] = true;
current.push_back(nums[i]);
// 继续继续下一个选择
backback(nums, current, resut, used);
// 回溯:移除当前数字并标记为未使用
current.pop_back();
used[i] = false;
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
vector<int> current;
vector<bool> used(nums.size(), false);
backback(nums, current, result, used);
return result;
}
};
思路分析2（直接使用全排列函数）：
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(),nums.end());
do{
res.push_back(nums);
}while(next_permutation(nums.begin(),nums.end()));
return res;
}
};
2.子集
思路分析（回溯）：
- 在每次调用backback时，先将子集current加入到result中；
- 然后从当前索引indxe开始遍历nums，选择一个元素加入current再递归调用backback；
- 递归结束后，移除最后一个元素（回溯），继续尝试其它可能的子集
具体实现代码（详解版）：
class Solution {
public:
void backback(vector<int>& nums, int index, vector<int>& current,
vector<vector<int>>& result) {
// 将当前子集加入结果集中
result.push_back(current);
// 从当前所有开始，遍历每个元素
for (int i = index; i < nums.size(); i++) {
// 选择当前元素
current.push_back(nums[i]);
// 递归生成包含当前元素的子集
backback(nums, i + 1, current, result);
// 回溯，移除当前元素
current.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> result;
vector<int> current;
backback(nums, 0, current, result);
return result;
return result;
}
};
3.电话号码的字母集合
思路分析：这是一个典型的回溯问题，因为我们需要在每一层递归中分别处理不同的数字，并组合出对应的字母。每个数字可以对应多个字母，因此我们可以使用递归或回溯法，将每一位数字的所有字母组合起来。
- 回溯法的思路：
- 递归构建路径：每次递归，我们处理一个数字，尝试将该数字对应的每个字母加入到当前组合中；
- 深入递归：每选择一个字母后，将组合的路径传递到下一层递归中，处理下一个数字的选择；
- 回溯撤销选择：在递归完成回退时，撤销最后一步操作，以便尝试当前数字对应其它字母的组合；
具体实现代码（详解版):
class Solution {
public:
void backtracking(string& digits, int index,
unordered_map<char, string> phoneMap, string& current,
vector<string>& result) {
// 收集结果
if (index == digits.size()) {
result.push_back(current);
return;
}
// 获取当前数字对应的字母
char digit = digits[index];
const string& letters = phoneMap.at(digit);
// 遍历当前数字的所有可能字母
for (char letter : letters) {
current.push_back(letter); // 选择一个字母
backtracking(digits, index + 1, phoneMap, current, result); // 递归
current.pop_back(); // 回溯
}
}
vector<string> letterCombinations(string digits) {
if (digits.empty())
return {};
// 数字到字母的映射
unordered_map<char, string> phoneMap = {{'2', "abc"},
{'3', "def"},
{'4', "ghi"} ,{'5', "jkl"},
{'6', "mno"},
{'7', "pqrs"}, {'8', "tuv"},
{'9', "wxyz"}};
vector<string> result;
string current;
backtracking(digits, 0, phoneMap, current, result);
return result;
}
};
4.组合总和
这是一个典型的组合求和问题，在这里，我们需要找到所有可能的组合，使得数组中的元素之和等于给定的目标值 target。在组合中，数组中的每个元素可以被选择任意次，但组合中的元素顺序不影响结果的唯一性。
思路分析：这个问题可以通过回溯算法来解决。我们需要遍历每个元素，从当前元素开始进行递归计算，探索所有可能的组合。在递归过程中，我们不断减小目标值 target，直到 target 等于 0，这时说明找到了一组解。
- 递归与回溯
- 递归函数通过不断地选择当前数字并递归减小target的值，从而构建组合；
- 如果target减少到0，说明找到一个组合，将其加入结果列表；
- 如果 target 小于 0，则表示当前组合不符合要求，直接回溯。
- 去重
- 每次递归调用都可以从当前数字开始进行选择（包括重复选择当前数字），而不需要从头开始，避免重复组合的出现
具体实现代码（详解版）：
class Solution {
public:
void backtracking(vector<int>& candidates,int target,int index,vector<vector<int>>& result,vector<int>& current){
//递归终止条件
if(target ==0 ){
result.push_back(current);//找到一个满足条件的组合，加入结果集
return;
}
for(int i = index ; i < candidates.size() ; i ++){
//选择当前元素
if(candidates[i] <= target){//当前数字可以加入组合
current.push_back(candidates[i]);//做出选择
backtracking(candidates,target - candidates[i],i,result,current);
current.pop_back();//回溯
}
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> result;
vector<int> current;
backtracking(candidates,target,0,result,current);
return result;
}
};
5.括号生成
要生成所有可能的有效括号组合，我们可以使用回溯算法。对于给定的 n 对括号，生成的组合必须满足以下条件：
- 括号对数匹配，即最终的左括号和右括号的数量相等；
- 在生成工过程中，任何前缀的右括号数都不能超过左括号数，这样才能保证括号的有效性；
思路分析：
- 递归和回溯：使用递归来构建括号组合字符串；
- 控制左括号和右括号数量：
- 如果左括号数量小于n，可以添加左括号；
- 如果右括号数量小于左括号数量，可以添加右括号；
- 递归终止条件：当左右括号的数量都等于n时，说明生成了一个有效的括号组合，将其加入结果集中。
具体实现代码（详解版）：
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> result;
backtracking(result,"",0,0,n);
return result;
}
void backtracking(vector<string>& result,string current,int open,int close,int max){
if(current.size() == max * 2){//当生成的括号长度达到2 * n时，加入结果集
result.push_back(current);
return;
}
if(open < max){//只有当左括号数小于n时才能添加左括号
backtracking(result,current + "(",open + 1 ,close,max);
}
if(close < open){//只有当右括号数小于左括号数才能添加右括号
backtracking(result,current + ")",open,close + 1,max);
}
}
};