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);}}
};