java - 打印所有验证括号，这里的递归如何工作？

Question

实现一个算法来打印 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);
        }
    }
}

但我不太完全理解解决方案，尽管有人声称解释足够简单。 (此代码工作正常)

在我看来，这段代码的工作原理是当有更多的左括号时，然后添加左括号。所以，只有((()))的条件因为条件 如果 (l > 0 )出现在 r > 0 之前，因此，它应该总是先处理所有剩下的。

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

此外，如果有人能解释什么是时间/空间复杂度，那对我会有很大帮助。

提前致谢。

Answer 1

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

因为这棵树的深度(显然)最多为 2.count ，空间复杂度为O(count) .

因为每个函数调用都可以添加一个 (或 ) ，时间复杂度至多为O(2<sup>number of function calls</sup>) = O(2<sup>2 count</sup>) .

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