Найдите все комбинации k-битных чисел с набором n бит, где 1 <= n <= k в отсортированном порядке

Для числа k найдите все возможные комбинации k-битных чисел с набором n бит, где 1 <= n <= k. Решение должно сначала вывести все числа с одним установленным битом, а затем числа с двумя установленными битами,… до чисел, все k-биты которых установлены. Если два числа имеют одинаковое количество установленных битов, то первым должно идти меньшее число.

Примеры:

Ввод: K = 3
Выход: 
001 010 100 
011 101 110 
111 

Ввод: K = 4
Выход: 
0001 0010 0100 1000 
0011 0101 0110 1001 1010 1100 
0111 1011 1101 1110 
1111 

Ввод: K = 5
Выход: 
00001 00010 00100 01000 10000 
00011 00101 00110 01001 01010 01100 10001 10010 10100 11000 
00111 01011 01101 01110 10011 10101 10110 11001 11010 11100 
01111 10111 11011 11101 11110 
11111 

Нам нужно найти все возможные комбинации k-битных чисел с n установленными битами, где 1 <= n <= k. Если мы внимательно проанализируем, то увидим, что проблему можно разделить на подзадачи. Мы можем найти все комбинации длины k с n единицами, добавив 0 ко всем комбинациям длины k-1 с n единицами и 1 ко всем комбинациям длины k-1 с n-1. Мы можем использовать динамическое программирование, чтобы сохранить решения подзадач.

Ниже представлена реализация вышеупомянутой идеи на С ++ -

Выход:

00000 
00001 00010 00100 01000 10000 
00011 00101 00110 01001 01010 01100 10001 10010 10100 11000 
00111 01011 01101 01110 10011 10101 10110 11001 11010 11100 
01111 10111 11011 11101 11110 
11111

Эта статья предоставлена Адитьей Гоэлем . Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.