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

Implement an algorithm to print all valid (e.g., properly opened and closed) combinations of n-pairs of parentheses. EXAMPLE: input: 3 (e.g., 3 pairs of parentheses) output: ()()(), ()(()), (())(), ((()))

答案是：

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);
        }
    }
}

但我不很充分认识解决方案，虽然有人声称的解释是够直白。 （此code正常工作）

But i dont quite fully understand the solution although someone claims the explanation is straightforward enough. (this code works fine)

在我看来，这code的工作原理时，有更多的左括号，然后添加左括号。如此，唯一的条件（（（）））怎么把条件     如果（升> 0） 出现R> 0之前，因此，它应该首先处理所有左侧的。

In my opinion, this code works as when there is more left parentheses, then add the left parentheses. so, only condition of （（（））） coz the condition if (l > 0 ) appear before r > 0 , so, it should always handle all the left ones first.

但是，这code如何处理这种情况（）（（））？我调试这个code，而且发现后，打印出（（（）））。它跑到L = 1的情况下，R = 3，海峡=（（（））），并数= 2，这没有道理给我。

But how this code handle this situation "()(())"? i debug this code, and find out that after it prints out "((()))". it went to the situation of l =1, r =3, and str="((()))" and count = 2. which doesnt make sense to me.

另外，如果有人能解释什么是时间/空间复杂度，这将是对我来说没什么太大的帮助。

Also, if someone can explain what is the time/space complexity, that would be much helpful for me.

在此先感谢。

推荐答案

我画了一棵树来说明如何托架越来越为写数= 3 。再$ P $每个节点psents一个函数调用，它的文字是一个（或），这取决于什么调用函数添加。叶子那里得到打印的电话。

I drew a tree to show how the brackets are getting written for count = 3. Each node represents a function call, with its text being a ( or ), depending on what the calling function added. The leaves are the calls where it gets printed.

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

Since the depth of this tree is (obviously) at most 2.count, the space complexity is O(count).

由于每个函数调用可以添加一个（或），时间复杂度为最多 O（2 的函数调用数） = 0（2 2计数）。

Since every function call can either add a ( or a ), the time complexity is at most O(2number of function calls) = O(22 count).

但是，由于呼叫是有条件的，时间复杂性最终被以下，更具体地，它似乎是围绕 0（2 2计数 /计数），虽然我还没有证明这一点。

But, since the calls are conditional, the time complexity ends up being less, more specifically, it appears to be around O(22 count/count), though I'm yet to prove that.