泵网站建设,正能量网站大全,长宁区网站建设网页制,北京做网站比较好的公司1、含有重复元素集合的组合 给定一个可能有重复数字的整数数组 candidates 和一个目标数 target #xff0c;找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用一次#xff0c;解集不能包含重复的组合。 【题目传送门】 思…1、含有重复元素集合的组合 给定一个可能有重复数字的整数数组 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用一次解集不能包含重复的组合。 【题目传送门】 思路还是典型的DFS算法用set过滤掉相同组合的列表
class Solution {
public:int N;int t;vectorvectorint ans;setvectorint set_ans;vectorinttemp;void dfs(vectorintc,int index,int sum){temp.emplace_back(c[index]);if(sumt){set_ans.insert(temp);// ans.emplace_back(temp);}else if(sumt){for(int iindex1;iN;i){if(sumc[i]t){break;}else{dfs(c,i,sumc[i]);}}}temp.pop_back();}vectorvectorint combinationSum2(vectorint candidates, int target) {ttarget;Ncandidates.size();sort(candidates.begin(),candidates.end());for(int i0;iN;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:vectorvectorint ans;vectorvectorint permute(vectorint 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:vectorvectorint ans;vectorvectorint permuteUnique(vectorint 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:vectorstringans;string temp;int N;void dfs(int len,int left,char tail){temptail;//couttemp\n;if(lenN){ans.emplace_back(temp);}else if(lenN){if(left1(N1)){dfs(len1,left1,();}if((len-left)1(N1)(left(len-left1))){dfs(len1,left,));}}temp.pop_back();}vectorstring generateParenthesis(int n) {//生成有效的括号组合Nn1;dfs(1,1,();return ans;}
};
