2.1 All valid permutation of parentheses I

Assumption: pairs of () > 0

Input: int n number of pairs of parentheses { (), (), () }

Output: List<String> all permutations

Solution:

1. n * 2 levels of the recursion tree, each level considers one position

2. 2 states: add "(" or add ")"

3. When adding a new ")", need to pair up with "(" by checking the # of "(" added so far

Need: remaining # of left "(", and remaining # of right ")"

if left > 0 && left < right, can consider adding ")"

if left > right, cannot add ")"

4. Stop condition: when all pairs are used, left = right == 0.

TC: 2 * 2^n = O(2^n)

SC: 2 * n = O(n)

public List<String> validParentheses(int n) {
   List<String> res = new ArrayList<>();
   char[] cur = new char[n * 2]; 
   helper(cur, n, n, 0, res);
   return res;
 }

 private void helper(char[] cur, int left, int right, int index, List<String> res) {
   //base case
   if (left == 0 && right == 0) {
     res.add(new String(cur));
     return;
   }
   if (left > 0) {
     cur[index] = '(';
     helper(cur, left - 1, right, index + 1, res);
   }
   if (right > left) {
     cur[index] = ')';
     helper(cur, left, right - 1, index + 1, res);
   }
 }