Subsets--LeetCode ╰半橙微兮° 2022-08-07 11:44 157阅读 0赞 # 题目: # Given a set of distinct integers, S, return all possible subsets. Note: * Elements in a subset must be in non-descending order. * The solution set must not contain duplicate subsets. For example, If S = `[1,2,3]`, a solution is: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ] 思路:第一个使用组合的思想,从这个数组中挑选出1,2,3,...n个元素的组合 第二个思想是递归,这个元素放或者不放 #include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; void helper(vector<int>& vec,int begin,int& num,vector<int>& subset) { if(begin >= vec.size() || num<0 ) return ; subset.push_back(vec[begin]); num--; if(num == 0) { int i; for(i=0;i<subset.size();i++) cout<<subset[i]<<" "; cout<<endl; } helper(vec,begin+1,num,subset); subset.pop_back(); num++; helper(vec,begin+1,num,subset); } void Combination(vector<int>& vec,int k) { if(vec.size()==0 || k <0) return ; vector<int> subset; sort(vec.begin(),vec.end()); helper(vec,0,k,subset); } void Subsets(vector<int>& vec) { int i; for(i=0;i<=vec.size();i++) Combination(vec,i); } void generate(vector<int> res, vector<int> &S, int i) { if(i == S.size()) { for(int j=0;j<res.size();j++) cout<<res[j]<<" "; cout<<endl; //return; } else { generate(res, S, i+1); res.push_back(S[i]); generate(res, S, i+1); } } void SubsetSecond(vector<int>& vec) { if(vec.size()<=0) return; sort(vec.begin(),vec.end()); vector<int> result; generate(result,vec,0); } int main() { int array[]={1,2,3}; vector<int> vec(array,array+sizeof(array)/sizeof(int)); SubsetSecond(vec); return 0; }
还没有评论,来说两句吧...