Leetcode Day5 含有重复元素集合的组合+

1、含有重复元素集合的组合

给定一个可能有重复数字的整数数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次，解集不能包含重复的组合。
【题目传送门】

思路：还是典型的DFS算法，用set过滤掉相同组合的列表

class Solution {
public:int N;int t;vector<vector<int> >ans;set<vector<int> >set_ans;vector<int>temp;void dfs(vector<int>&c,int index,int sum){temp.emplace_back(c[index]);if(sum==t){set_ans.insert(temp);// ans.emplace_back(temp);}else if(sum<t){for(int i=index+1;i<N;i++){if(sum+c[i]>t){break;}else{dfs(c,i,sum+c[i]);}}}temp.pop_back();}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {t=target;N=candidates.size();sort(candidates.begin(),candidates.end());for(int i=0;i<N;i++){if(candidates[i]>t){break;}else{dfs(candidates,i,candidates[i]);}}for(auto v:set_ans){ans.emplace_back(v);}return ans;}
};

2、没有重复元素集合的全排列

给定一个不含重复数字的整数数组 nums ，返回其 所有可能的全排列 。可以 按任意顺序 返回答案。
【题目传送门】

思路：可以借用C++自带的next_permutation函数来完成这个DFS的过程

class Solution {
public:vector<vector<int> >ans;vector<vector<int>> permute(vector<int>& nums) {//全排列sort(nums.begin(),nums.end());do{ans.emplace_back(nums);}while(next_permutation(nums.begin(),nums.end()));return ans;}
};

3、含有重复元素集合的全排列

给定一个可包含重复数字的整数集合 nums ，按任意顺序 返回它所有不重复的全排列。
【题目传送门】

思路同上一题

class Solution {
public:vector<vector<int> >ans;vector<vector<int>> permuteUnique(vector<int>& nums) {//全排列sort(nums.begin(),nums.end());do{ans.emplace_back(nums);}while(next_permutation(nums.begin(),nums.end()));return ans;}
};

4、生成匹配的括号

正整数 n 代表生成括号的对数，请设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
【题目传送门】

class Solution {
public:vector<string>ans;string temp="";int N;void dfs(int len,int left,char tail){temp+=tail;//cout<<temp<<"\n";if(len==N){ans.emplace_back(temp);}else if(len<N){if(left+1<=(N>>1)){dfs(len+1,left+1,'(');}if((len-left)+1<=(N>>1)&&(left>=(len-left+1))){dfs(len+1,left,')');}}temp.pop_back();}vector<string> generateParenthesis(int n) {//生成有效的括号组合N=n<<1;dfs(1,1,'(');return ans;}
};