Write a program to print all N-digit binary numbers with k-bits set where k ranges from 1 to N. Numbers with same number of bits set should be printed together and in ascending order.

4-digit binary numbers are –

(k = 1) 0001 0010 0100 1000

(k = 2) 0011 0101 0110 1001 1010 1100

(k = 3) 0111 1011 1101 1110

(k = 4) 1111

5-digit binary numbers are –

(k = 1) 00001 00010 00100 01000 10000

(k = 2) 00011 00101 00110 01001 01010 01100 10001 10010 10100 11000

(k = 3) 00111 01011 01101 01110 10011 10101 10110 11001 11010 11100

(k = 4) 01111 10111 11011 11101 11110

(k = 5) 11111

The idea is to use `std::next_permutation` that generates the next greater lexicographic permutation of a string. To print all numbers with k-bit set in ascending order, we set last k bits of a N-digit number to 1 and then use `std::next_permutation` to print numbers in lexicographical order.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include <iostream> #include <algorithm> using namespace std; // Function to find all N-digit binary numbers with k-bits set where // k ranges from 1 to N void printAllCombinations(int N) { // string to store N-digit binary number string str, curr; // construct N-digit binary number filled with all 0's int j = N; while (j--) { str.push_back('0'); } // print all numbers with k-bit set together in ascending order for (int k = 1; k <= N; k++) { // set last k bits to '1' str[N - k] = '1'; curr = str; cout << "(k = " << k << ") " ; // use std::next_permutation to print string lexicographically do { cout << curr << " "; } while (next_permutation(curr.begin(), curr.end())); cout << endl; } } // main function int main() { int N = 4; printAllCombinations(N); return 0; } |

`Output:`

(k = 1) 0001 0010 0100 1000

(k = 2) 0011 0101 0110 1001 1010 1100

(k = 3) 0111 1011 1101 1110

(k = 4) 1111

The time complexity of above solution is O(N^{2}) and auxiliary space used by the program is O(N) where `N` is the number of digits..

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

I believe the time complexity is O(2^n), and the space complexity is O(n) here.

You’re right. We have updated the space complexity. Many thanks 🙂