Generate N valid parentheses I

Given N pairs of parentheses “()”, return a list with all the valid permutations.

Assumptions

• N > 0

Examples

• N = 1, all valid permutations are ["()"]

• N = 3, all valid permutations are ["((()))", "(()())", "(())()", "()(())", "()()()"]

Solution: Recursive DFS

Base Case: N left and N right parentheses have been made

Recursive rule:

1. Add until N ' ( '

2. Match with ' ) '

3. delete previous ' ( '

4. Match with ' ) '

Recursive Tree:

                                          (
                           ((                            ()
                      (((      (()                    ()(  
                ((()       (()(  (())             ()((   ()()
          ((())       (()()         (())(      ()(())      ()()(
   ((()))       (()())                (())()                   ()()()

Implementation:

public void genParentheses(int n, int left, int right, StringBuilder sb){
    if (left == n && right == n){
        System.out.println(sb);
        return;
    }
    
    if ( l < n ){
        sb.append('(');
        genParentheses(n, left + 1, right, sb);
        sb.deleteCharAt(sb.length() - 1);
    }
    
    if ( r < l ){
        sb.append(')');
        genParentheses(n, left, right + 1, sb);
        sb.deleteCharAt(sb.length() - 1);
    }
}     

Time complexity: O(2^parentheses * 2 * ) = O(2^2N * N)