# 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)**