c++recursionvectorstl-algorithm

superset algorithm using stl giving duplicate subsets


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);
    }
}

Solution

  • 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;
    }