Simple and optimized recursive solution based on generating bit strings


  • 0
    M

    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.

Log in to reply
 

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