## Saturday, August 20, 2016

### 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