CODEWITHSUNDEEP
c++algorithmrecursion
richardzrc
richardzrc

Reputation: 9

combinations of k-tuple from n elements set by recursive

#include <vector>
#include <iostream>
using namespace std;

void SubSetNum(bool * select, int*a, int selectk, int k, int selectn, int n )// depthk to 
{
    if(k>n) return;
    if(selectn==n)
    {   
        if(selectk==k)
        {
            for(int i=0;i<n;i++)
                if(select[i]==true)
                    cout<<a[i];
            cout<<endl;
        }
        return;
    }

    select[selectk]=false;
    SubSetNum(select,a,selectk,k,selectn+1,n);
    select[selectk]=true;
    SubSetNum(select,a,selectk+1,k,selectn+1,n);

}

int main()
{
    int k=3;
    int n=5;
    int a[]={1,5,8,10,13};
    //while(cin>>k)
    {
        bool *select=new bool[n];
        memset(select,0,sizeof(bool)*n);
        SubSetNum(select,a,0,k,0,n);
        delete []select;
    }
    return 0;
}

This a question, that I want to get k elements from n elements set.

But it prints out incorrect answer? I am always confused when I design recursive algorithms...Especially the parameter of functions, if or not return value, and so on, thus I always try to forcely remember the code in textbook.

Upvotes: 0

Views: 281

Answers (1)

Beta
Beta

Reputation: 99144

Your mistake is here:

select[selectk]=false;                                                                   
...
select[selectk]=true;

It should be this:

select[selectn]=false;
...
select[selectn]=true;

I believe the cause of the mistake was a failure to remember what the variables represent. The variable selectn is the index of the element being included or excluded. The variable selectk is the number of elements already included. It does not make sense to use selectk as an index into a.

Upvotes: 1

Related Questions