Simple and optimized recursive solution based on generating bit strings

  • 0

    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;
    	int elements_left = n - index; 
    	// when index is 0, there are n elements left to choose from.
    	if(elements_left > (k - ones_count))
    	// now is the time to print.
    	vector<int> choices;
    	for(int i=0;i<n;i++)

    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.