Найти двоичные перестановки заданного размера, отсутствующие в массиве

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

Примеры:

Input: N = 3, arr[] = {“101”, “111”, “001”, “010”, “011”, “100”, “110”}
Output: 000
Explanation: Only 000 is absent in the given array.

Input: N = 2, arr[] = {“00”, “01”}
Output: 10 11

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

• Инициализируйте unordered_set строк S , который хранит все строки в массиве arr[] .
• Инициализируйте переменную, скажем, total , и установите ее как степень 2 ^N , где N — размер строки.
• Переберите диапазон [0, total), используя переменную i , и выполните следующие шаги:
  • Инициализируйте пустую строковую переменную num как «» .
  • Выполните итерацию в диапазоне [N – 1, 0], используя переменную j , и если значение побитового И для i и 2 ^j истинно , затем вставьте символ 1 в строку num . В противном случае нажмите символ 0 .
  • Если число num отсутствует в наборе S , то выведите строку num как одну из результирующей строки.
• После выполнения вышеуказанных шагов, если в массиве присутствуют все возможные двоичные строки, выведите «-1» .

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

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