algorithm - 括号对的递归算法

Question

我试图回答以下问题:“实现一个算法来打印 n 对括号的所有有效(即正确打开和关闭)组合。”

回答说:“我们的第一个想法可能是应用递归方法，我们通过向 f(n - 1) 添加一对括号来构建 f(n) 的解决方案。我们可以通过插入一个每对现有括号内的一对括号，以及字符串开头的一个括号。”

我很难理解我们如何保证在每一对现有的括号内插入一对括号，以及在字符串的开头插入一对括号，将创建所有可能的解决方案。我们怎么知道这不会产生重复的解决方案，或者遗漏一些正确的解决方案？有人可以解释一下吗？

(引述来源:Cracking the Coding Interview)

Answer 1

您描述的方法适用于 f(1) 和 f(2)。对于 n > 2，它不会遗漏任何一个，但会产生重复。

对于 f(3)，这是开始生成重复项的时间。在 f(2) 的基础上，您有“()()”和“(())”这两个解决方案。当您在该算法之后插入括号时，您最终会生成“()(())”这两个解决方案。由于这个重复项，您最终得到 f(3) 的 6 个解而不是实际的 5 个。

如果将该算法应用于 f(5)，它会生成 f(1) 到 f(5) 的 33 个总解。应该只有 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