Найдите K-й лексикографически наименьший подмассив

Дан массив arr[] из N целых чисел, задача состоит в том, чтобы найти K ^-е лексикографически наименьшее подмножество данного массива.

Пример:

Input: arr[] = {5, 15}, K = 2
Output: 5 15
Explanation: The subsets of the given set in lexicographic order are {5}, {5, 15}, and {15}. Hence the 2nd smallest subset is {5, 15}.

Input: arr[] = {1, 2, 3, 4}, K = 5
Output: 1 2 4

Подход: Данную задачу можно решить, сгенерировав весь набор мощностей заданного массива, а затем отсортировав подмножества набора мощностей в лексикографическом порядке. Следовательно, подмножество с K ^-м индексом отсортированного набора мощностей является искомым ответом.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N * 2 ^N )
Вспомогательное пространство: O(2 ^N )