Time complexity of combinations of n pairs of parentheses I have the following code snippet for combinations of n pairs of parentheses.

def parens(n):
    if n &lt;= 0:
        return ['']
    else:
        combinations = []
        helper('', n, n, combinations)
        return combinations


def helper(string, left, right, combinations):
    if left &lt;= 0 and right &lt;= 0:
        combinations.append(string)
    else:
        if left &gt; 0:
            helper(string + '(', left - 1, right, combinations)
        if right &gt; left and right &gt; 0:
            helper(string + ')', left, right - 1, combinations)


What's the reasonable estimation of the time complexity of it?

My trials:


(2n)!/n!n! since it's permutations of multisets with more limitations.
Resolve recurrence: T(n) = 2T(n-1) => O(2^n).
Actually, for every combination of parenthesis, your algorithm performs $\Theta(n)$ amount of work (to build the string and append it to your list of combinations).

The number of valid combinations of $n$ pairs of parenthesis is the $n$'th Catalan Number $C_n = \frac{1}{n+1}\binom{2n}{n}$.

Thus, your algorithm runs in $\Theta(nC_n)$ which is also equal to $\Theta(\frac{4^n}{\sqrt{n}})$, because $C_n$ grows as $\Theta(\frac{4^n}{n^{3/2}})$ (see the linked Wikipedia article).