Количество уникальных подпоследовательностей из заданного числа, которые являются степенью 2

Для заданной строки S размера N , содержащей цифры в диапазоне [0-9] , задача состоит в том, чтобы напечатать количество всех уникальных подпоследовательностей строки, которые являются степенью числа 2 .

Примеры:

Input: S = “1216389”
Output: 5
Explanation:
All the possible unique subsequences that are power of 2 are: {1, 2, 16, 128, 8}

Input: S = “12”
Output: 2
Explanation:
All the possible unique subsequences that are power of 2 are: {1, 2}.

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

• Инициализируйте набор, скажем, allUniqueSubSeq для хранения подпоследовательности, которая является степенью числа 2 .
• Определите рекурсивную функцию, скажем, uniqueSubSeq(S, ans, index) и выполните следующие шаги:
  • Базовый случай: если индекс равен N, то если (int)ans является степенью числа 2, то вставьте ans в набор allUniqueSubSeq .
  • В противном случае возможны два случая:
    • Если S[index] добавляется в строку ans , вызовите функцию uniqueSubSeq с параметрами S , ans + S[index] и index+1.
    • Если S[index] не добавляется в строку ans , то вызовите функцию uniqueSubSeq с параметрами S , ans и index + 1 .
• Наконец, после выполнения вышеуказанных шагов вызовите функцию uniqueSubSeq(S, "", 0), а затем напечатайте allUniqueSubSeq.size() в качестве ответа.

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

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