[Leetcode] 07/06 [String] Generate Parentheses

Recursive Time:O(); Space:O() Logic: ==> (( => (( ) => (( )) ( L2 R0 L2 R1 L2 R2 L1 R0 ==> ( ) => ( ) ( => ( ) ( ) L1 R1 L2 R1 L2 R2 NOTE: C_0 =1, C_1 = 1, C_2 =2 ,C_3 = 5, C_4 = 14 C_0 =1, C_n+1 = [i=0~n]signma(C_i*C_n-i), for n >= 0 C3 = C_0*C2 + C_1*C_1 + C_2*C_0 = 2 + 1 + 2 = 5 C_n+1 = ( 2(2*n+1) / n+2 )* C_n the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involving recursively-defined objects. Re-interpreting the symbol X as an open parenthesis and Y as a close parenthesis, Cn counts the number of expressions containing n pairs of parentheses which are correctly matched: C_0 = 1 \quad \mbox{and} \quad C_{n+1}=\sum_{i=0}^{n}C_i\,C_{n-i}\quad\text{for }n\ge 0;

public class Solution {
    public List generateParenthesis(int n) {
        ArrayList res = new ArrayList();
        if ( n < 0 )
        {
            return res;
        }    
        helper( n,n, new String(), res );
        return res;
    }
    
    private void helper( int l, int r, String item, ArrayList res ) 
    {
        // Base case
        // remaining r should be greater or equal to l
        if ( r < l )
        {
            return;
        }
        // when consuming all l and r, return current combination
        if ( l == 0 && r == 0 )
        {
            res.add(item);
        }
        
        
        if (  l > 0 )
        {
            helper( l-1, r, item+"(", res);
        }
        if (  r > 0 )
        {
            helper(l, r-1, item+")", res);
        }
    }
}