【刷题篇】回溯算法(三)
文章目录
- 1、全排列
- 2、子集
- 3、找出所有子集的异或总和再求和
- 4、全排列 II
- 5、电话号码的字母组合
- 6、括号生成
1、全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
class Solution {
public:vector<vector<int>> ret;vector<int> path;//vector<bool> sign(7);并不能使用它，它并不能使用[],底层储存问题bool sign[7];vector<vector<int>> permute(vector<int>& nums) {dfs(nums);return ret;}void dfs(vector<int>& nums){if(nums.size()==path.size()){ret.push_back(path);return;}for(int i=0;i<nums.size();i++){if(sign[i]==false){path.push_back(nums[i]);sign[i]=true;dfs(nums);path.pop_back();sign[i]=false;}}}
};
2、子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的
子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
class Solution {
public:vector<vector<int>> ret;vector<int> path;vector<vector<int>> subsets(vector<int>& nums) {dfs(nums,0);return ret;}//解法一// void dfs1(vector<int> nums,int i)// {// if(i==nums.size())// {// ret.push_back(path);// return;// }// //选// path.push_back(nums[i]);// dfs(nums,i+1);// path.pop_back();// //不选// dfs(nums,i+1);// }//解法二void dfs(vector<int> nums,int pos){ret.push_back(path);for(int i=pos;i<nums.size();i++){path.push_back(nums[i]);dfs(nums,i+1);path.pop_back();}}
};
3、找出所有子集的异或总和再求和
一个数组的 异或总和 定义为数组中所有元素按位 XOR 的结果；如果数组为 空 ，则异或总和为 0 。
例如，数组 [2,5,6] 的 异或总和 为 2 XOR 5 XOR 6 = 1 。
给你一个数组 nums ，请你求出 nums 中每个 子集 的 异或总和 ，计算并返回这些值相加之 和 。
注意：在本题中，元素 相同 的不同子集应 多次 计数。
数组 a 是数组 b 的一个 子集 的前提条件是：从 b 删除几个（也可能不删除）元素能够得到 a 。
class Solution {
public:// vector<int> ret;// vector<int> path;// int subsetXORSum(vector<int>& nums) {// dfs(nums,0);// int sum=0;// for(int i=0;i<ret.size();i++)// {// sum+=ret[i];// }// return sum;// }// void dfs(vector<int> nums,int pos)// {// int sum=0;// for(int i=0;i<path.size();i++)// {// sum^=path[i];// }// ret.push_back(sum);// for(int i=pos;i<nums.size();i++)// {// path.push_back(nums[i]);// dfs(nums,i+1);// path.pop_back();// }// }int sum=0;int path=0;int subsetXORSum(vector<int> nums){dfs(nums,0);return sum;}void dfs(vector<int> nums,int pos){sum+=path;//每次开始的节点都是我们需要的for(int i=pos;i<nums.size();i++){path^=nums[i];dfs(nums,i+1);path^=nums[i];//恢复现场}}
};
4、全排列 II
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
class Solution {
public:vector<vector<int>> ret;vector<int> path;bool check[8];vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(),nums.end());//方便后面处理分支dfs(nums,0);return ret;}void dfs(vector<int> nums,int pos){if(pos==nums.size())ret.push_back(path);for(int i=0;i<nums.size();i++){//剪枝方法一，只关心合法分支// if(check[i]==false&&(i==0||nums[i]!=nums[i-1]||(check[i-1]==true&&nums[i]==nums[i-1])))// {// check[i]=true;// path.push_back(nums[i]);// dfs(nums,pos+1);// check[i]=false;// path.pop_back();// }//剪枝方法二,只关心不合法分支if(check[i]==true||(i!=0&&nums[i]==nums[i-1]&&check[i-1]==false))continue;check[i]=true;path.push_back(nums[i]);dfs(nums,pos+1);check[i]=false;path.pop_back();}}
};
5、电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
class Solution {
public:string hash[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};vector<string> ret;string path;vector<string> letterCombinations(string digits) {if(digits.empty())return ret;dfs(digits,0);return ret;}void dfs(string digits,int pos){if(pos==digits.size()){ret.push_back(path);return;}for(auto a : hash[digits[pos]-'0']){path.push_back(a);dfs(digits,pos+1);path.pop_back();}}
};
6、括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
class Solution {
public:int left,right,n;vector<string> ret;string path;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--;}}
};