I am trying to find superset of a given vector. I do this by recursion. Going iteratively I remove a value and then call the function with new set. I get all sets but they are repeated. Eg for 5 elements, there should 32 to 31 subsets, while I get about 206 subsets. This is my code
using namespace std;
int iter = 1;
void display(vector<int> &v)
{
cout<<"case#"<<iter++<<": ";
vector<int>::iterator i;
for(i=v.begin();i!=v.end();i++)
cout<<*i<<" ";
cout<<endl;
}
void gen( vector<int> &v)
{
if(v.size()==0) return;
display(v);
vector<int>::iterator j,i;
for(i=v.begin();i!=v.end();i++)
{
vector<int> t(v);
j = find(t.begin(),t.end(),*i);
t.erase(j);
gen(t);
}
}
You don't have to pass v as argument everytime. Just make it global.
And try every combination to find all subset.
Complexity : 2^N
vector<int>v;
int iter = 1;
int take[20];
void display()
{
cout<<"Case#"<<iter++<<": ";
int n=v.size();
for(int i=0;i<n;i++)
{
if(take[i])
cout<<v[i]<<" ";
}
cout<<endl;
}
void gen(int x)
{
if(x==v.size())
{
display();
return;
}
int i,j,n=v.size();
take[x]=1;
gen(x+1);
take[x]=0;
gen(x+1);
}
int main()
{
int i,j,n;
cin>>n;
for(i=0;i<n;i++)
{
cin>>j;
v.push_back(j);
}
gen(0);
return 0;
}