4

实现一个算法来打印所有有效（例如，正确打开和关闭）的 n 对括号组合。示例：输入：3（例如，3 对括号）输出：()()()、()(())、(())()、((()))

答案是 ：

private static void printPar(int count)
{
    char[] str = new char[count*2];
    printPar(count,count,str, 0);
}

private static void printPar(int l, int r, char[] str, int count)
{
    if(l < 0 || r < l)
        return;

    if (l ==0 && r == 0)
    {
        System.out.println(str);
    }
    else
    {
        if (l > 0 )
        {
            str[count] = '(';
            printPar(l-1, r, str, count + 1);
        }

        if (r > 0)
        {
            str[count] = ')';
            printPar(l, r-1, str, count + 1);
        }
    }
}

但是我并不完全理解这个解决方案，尽管有人声称这个解释很简单。（此代码工作正常）

在我看来，这段代码在有更多左括号时起作用，然后添加左括号。所以，只有（（（）））的条件，因为条件 if (l > 0 ) 出现在 r > 0 之前，所以，它应该总是先处理所有左边的。

但是这段代码如何处理这种情况“（）（（））”？我调试了这段代码，并在它打印出“（（（）））”之后发现。它去了l = 1，r = 3和str =“（（（）））”和count = 2的情况。这对我来说没有意义。

另外，如果有人可以解释什么是时间/空间复杂度，那对我来说会很有帮助。

提前致谢。

4

3 回答 3

7

我画了一棵树来展示括号是如何写的count = 3。每个节点代表一个函数调用，其文本为 a(或)，具体取决于调用函数添加的内容。叶子是打印它的调用。

由于这棵树的深度（显然）最多2.count为 ，空间复杂度为O(count)。

由于每个函数调用都可以添加 a(或 a )，因此时间复杂度最多为 = 。O(2number of function calls)O(22 count)

但是，由于调用是有条件的，因此时间复杂度最终会降低，更具体地说，它似乎在 左右，尽管我还没有证明这一点。O(22 count/count)

于 2013-10-26T18:57:56.120 回答
3

在递归时，算法会跟踪剩余的左括号数 (l)、剩余的右括号数 (r)、到目前为止的结果 (str) 和生成的括号数 (count)。

如果没有括号，则打印结果。

如果至少保留一个左括号，则使用它，并且该函数递归生成以当前前缀开头的所有结果

然后，如果至少保留一个右括号，并且至少一个左括号没有闭合，则使用一个右括号，并且函数递归。

但是这段代码如何处理这种情况“（）（（））”？我调试了这段代码，并在它打印出“（（（）））”之后发现。它去了l = 1，r = 3和str =“（（（）））”和count = 2的情况。这对我来说没有意义。

打印后((()))使用参数调用函数1时，3,((()))和2,count=2表示唯一有效的部分str是((。然后，它)在使用参数1、2、(()和递归之前继续添加 a 3，从而(()())打印下一个组合，然后是()(())和()()()。

于 2013-10-26T19:05:00.660 回答
3

代码运行成功，因为它不允许 r < l。如果是这样，那么它只是丢弃组合并返回。这意味着右括号只能出现在左括号之后。

如果您还计算丢弃的递归调用，复杂性的顺序是(2n)!/( n! * n! ). 这是 n '(' 和 n ')' 的排列数。

如果您尝试跟踪代码，它将按如下方式运行：

(
 (
  (
   )
    )
     ) 
      ((()))
  )
   (
    )
     )
      (()())
   )
    (
     )
      (())()
 )
  (
   (
    )
     )
      ()(())
(
 )
  (
   )
    (
     )
      ()()()
于 2013-10-26T18:54:00.650 回答