# Simple and optimized recursive solution based on generating bit strings

• Key ideas:

As long as you have not chosen k elements, you still have to continue choosing. so place a 1.
As long there are more elements left to choose from, than there left to choose, you can place a 0.

``````void k_elements_chosen(int* bits,vector<vector<int> > &bigList,int index, int n, int k, int ones_count)
{
if(index < n)
{
if( ones_count < k)
{
// able to place a 1.
bits[index] = 1;
k_elements_chosen(bits,bigList,index+1,n,k,ones_count+1);
}

int elements_left = n - index;
// when index is 0, there are n elements left to choose from.
if(elements_left > (k - ones_count))
{
bits[index]=0;

k_elements_chosen(bits,bigList,index+1,n,k,ones_count);
}

}else{

// now is the time to print.
vector<int> choices;
for(int i=0;i<n;i++)
{

if(bits[i]==1)
{
choices.push_back(i+1);

}
}
bigList.push_back(choices);
}
}
``````

Calling it, 5 choose 2:

``k_elements_choose(bit_array,bigList,0,5,2,0); // initially ones_count is 0. nothing is chosen yet.``

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.