Рекурсивный алгоритм для пар круглых скобок

Question

Я пытаюсь ответить на следующий вопрос: «Внедрить алгоритм для печати всех допустимых (то есть правильно открытых и закрытых) комбинаций n-пар круглых скобок».

В ответ говорится: «Наша первая мысль может заключаться в применении рекурсивного подхода, где мы строим решение для f (n) путем добавления пар скобок к f (n - 1). Мы можем сделать это, вставив пара круглых скобок внутри каждой существующей пары круглых скобок, а также одна в начале строки. "

Мне сложно понять, как мы можем гарантировать, что вставка пары круглых скобок внутри каждой существующей пары круглых скобок, а также одна в начале строки, создаст все возможные решения. Как мы узнаем, что это не приведет к дублированию решений или не даст правильных решений? Может ли кто-нибудь объяснить это?

(Источник цитаты: Крекинг кодирвоание интервью)

Answer 1

подход вы описали отлично работает для F (1) и F (2). При n> 2 он не пропустит ни одного, но будет генерировать дубликаты.

Для f (3) это происходит при создании дубликатов. Основываясь на f (2), у вас есть 2 решения «()()» и «(())». Когда вы вставляете скобки в соответствии с этим алгоритмом, вы получаете оба из этих решений, генерирующих «() (())». Вы получаете 6 решений f (3) вместо фактических 5 из-за этого дубликата.

Если вы применяете алгоритм к f (5), он генерирует 33 полных решения функции f (1) через f (5). Там должно быть только 22 решения, поэтому вы получаете 10 дубликатов.

Существует очень распространенное рекурсивное решение, связанное с подсчетом открытия и закрытия нескольких скобок. Лучшее объяснение, которое я видел это на https://anonymouscoders.wordpress.com/2015/06/16/all-balanced-permutation-of-number-of-given-parentheses/

Вот пример одного из решений в C:

// Source: http://www.geeksforgeeks.org/print-all-combinations-of-balanced-parentheses/ 
# include<stdio.h> 
# define MAX_SIZE 100 

void _printParenthesis(int pos, int n, int open, int close); 

/* Wrapper over _printParenthesis()*/ 
void printParenthesis(int n) 
{ 
    if(n > 0) 
    _printParenthesis(0, n, 0, 0); 
    return; 
}  

void _printParenthesis(int pos, int n, int open, int close) 
{ 
    static char str[MAX_SIZE];  

    if(close == n) 
    { 
    printf("%s \n", str); 
    return; 
    } 
    else 
    { 
    if(open > close) { 
     str[pos] = '}'; 
     _printParenthesis(pos+1, n, open, close+1); 
    } 
    if(open < n) { 
     str[pos] = '{'; 
     _printParenthesis(pos+1, n, open+1, close); 
    } 
    } 
} 

/* driver program to test above functions */ 
int main() 
{ 
    int n = 4; 
    printParenthesis(n); 
    getchar(); 
    return 0; 
} 

Для справки, вот C# версии я сделал для предусмотренного алгоритма:

// Initial funtion call 
void f(int n) 
{ 
    f(1, n, ""); 
} 

// Recursive call 
void f(int n, int max, string output) 
{ 
    for (int i = 0; i < output.Length; i++) 
    { 
     if (output[i] == '(') 
     { 
      var inserted = output.Insert(i + 1, "()"); 
      Console.WriteLine(inserted); 
      if (n < max) 
       f(n + 1, max, inserted); 
     } 
    } 

    // Pre-pend parens 
    output = "()" + output; 
    Console.WriteLine(output); 
    if (n < max) 
     f(n + 1, max, output); 
} 

f(4); 

Ссылка: https://dotnetfiddle.net/GR5l6C