Time complexity for combination of parentheses

[admin]

I tried to do the classical problem to implement an algorithm to print all valid combinations of n pairs of parentheses.

I found this program (which works perfectly) :

public static void addParen(ArrayList<String> list, int leftRem, int rightRem, char[] str, int count) {
    if (leftRem < 0 || rightRem < leftRem) return; // invalid state

    if (leftRem == 0 && rightRem == 0) { /* all out of left and right parentheses */
        String s = String.copyValueOf(str);
        list.add(s);
    } else {
        if (leftRem > 0) { // try a left paren, if there are some available
            str[count] = '(';
            addParen(list, leftRem - 1, rightRem, str, count + 1);
        }
        if (rightRem > leftRem) { // try a right paren, if there’s a matching left
            str[count] = ')';
            addParen(list, leftRem, rightRem - 1, str, count + 1);
        }
    }
}

public static ArrayList<String> generateParens(int count) {
    char[] str = new char[count*2];
    ArrayList<String> list = new ArrayList<String>();
    addParen(list, count, count, str, 0);
    return list;
}

As I understand, the idea is that we will add left brackets whenever possible. For a right bracket, we will add it only if the remaining number of right brackets is greater than the left one. If we had used all the left and right parentheses, we will add the new combination to the result. We can be sure that there will not be any duplicate constructed string.

For me, this recursion, is like when we work with a tree for example and we do the pre order traversal for example : we go to a left node EACH time is possible, if not we go right, and then we try to go left just after this step. If we can’t, we "come back" and go right and we repeat the traversal. In my opinion, it's exactly the same idea here.

So, naively, I thought that the time complexity will be something like O(log), O(n.log) or something like that with logarithm. But, when I tried to search about that, I found something called "number of CATALAN", which we can use to count the number of combination of parentheses....(<a href="https://anonymouscoders.wordpress.com/2015/07/20/its-all-about-catalan/" rel="noreferrer">https://anonymouscoders.wordpress.com/2015/07/20/its-all-about-catalan/</a>)

What are the time complexity in your opinion? Can we apply the master theorem here or not?