Выведите все строки Balanced Brackets Strings, которые могут быть образованы заменой подстановочного знака '?'

Для данной строки str , содержащей символы '?', '(' и ')', задача состоит в том, чтобы заменить '?' символ с '(' или ')' и вывести все строки, содержащие сбалансированные скобки

Пример:

Input: str = “????”
Output:
()()
(())

Input: str = “(()?”
Output: (())

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

• Преобразуйте строку strin в массив символов, скажем, ch
• Передайте массив символов ch и индекс 0 в качестве параметров внутри рекурсивной функции и при каждом рекурсивном вызове выполните следующее:
  • Если индекс становится равным длине массива символов, то:
    • Проверьте, является ли массив символов сбалансированной строкой скобок
    • Если приведенное выше условие верно, то выведите строку
  • Если текущий символ ch[index] равен '(' или ')', выполните рекурсивный вызов следующего индекса
  • Если текущий символ ch[index] равен '?' тогда:
    • Замените его на '(' и выполните рекурсивный вызов следующего индекса
    • Замените его на ')' и выполните рекурсивный вызов следующего индекса.
    • Измените его обратно на '?' перед возвратом из функции

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

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