Find all combinations of k-bit numbers with n bits set where 1 <= n <= k in sorted order - GeeksforGeeks

Find all combinations of k-bit numbers with n bits set where 1 <= n <= k in sorted order - GeeksforGeeks
Given a number k, find all the possible combinations of k-bit numbers with n-bits set where 1 <= n <= k. The solution should print all numbers with one set bit first, followed by numbers with two bits set,.. up to the numbers whose all k-bits are set. If two numbers have the same number of set bits, then smaller number should come first.

We need to find all the possible combinations of k-bit numbers with n set bits where 1 <= n <= k. If we carefully analyze, we see that problem can further be divided into sub-problems. We can find all combinations of length k with n ones by prefixing 0 to all combinations of length k-1 with n ones and 1 to all combinations of length k-1 with n-1 ones. We can use Dynamic Programming to save solutions of sub-problems.

// maximum allowed value of K

#define K 16

// DP lookup table

vector<string> DP[K][K];

// Function to find all combinations k-bit numbers with

// n-bits set where 1 <= n <= k

void findBitCombinations(int k)

{

    string str = "";

     

    // DP[k][0] will store all k-bit numbers 

    // with 0 bits set (All bits are 0's)

    for (int len = 0; len <= k; len++)

    {

        DP[len][0].push_back(str);

        str = str + "0";

    }

     

    // fill DP lookup table in bottom-up manner

    // DP[k][n] will store all k-bit numbers 

    // with n-bits set

    for (int len = 1; len <= k; len++)

    {

        for (int n = 1; n <= len; n++)

        {

            // prefix 0 to all combinations of length len-1

            // with n ones

            for (string str : DP[len - 1][n])

                DP[len][n].push_back("0" + str);

            // prefix 1 to all combinations of length len-1

            // with n-1 ones

            for (string str : DP[len - 1][n - 1])

                DP[len][n].push_back("1" + str);

        }

    }

     

    // print all k-bit binary strings with

    // n-bit set

    for (int n = 1; n <= k; n++)

    {

        for (string str : DP[k][n])

            cout << str << " ";

        cout << endl;

    }

}

Read full article from Find all combinations of k-bit numbers with n bits set where 1 <= n <= k in sorted order - GeeksforGeeks