2.2 All permutations of parentheses II

Assumption: Given l pairs of (), m pairs of <>, and n pairs of {}, all pairs >= 0

Solution:

1. 2l + 2m + 2n levels in the recursion tree, each level consider one position

2. states/branches: 2 * types of parentheses at most

3. Stop condition: when all parentheses are used

4. Additional restriction:

5. Same type, left added > right added

6. left must match the type of right. The right parenthesis must match the most recently unclosed left parenthesis.

Data structure:

1. Use 1 stack to pair match;

2. When adding a new left, check left_added, push into stack, add it to sb

3. When adding a new right, check if it matches stack.peek()

4. If matches, stack.pop(), add to sb

5. If not, skip this branch

private static final char[] PS = new char[]{'(', ')', '<', '>', '{', '}'};

public List<String> validParentheses(int l, int m, int n) {
   int length = l * 2 + m * 2 + n * 2;
   int[] remain = new int[] {l, l, m, m, n, n};
   StringBuilder cur = new StringBuilder();
   Deque<Character> stack = new LinkedList<>();
   List<String> res = new ArrayList<>();
   helper(cur, stack, remain, length, res);
   return res;
 }

 private void helper(StringBuilder cur, Deque<Character> stack, int[] remain, int length, List<String> res) {
   //base case
   if (cur.length() == length) {
     res.add(cur.toString());
     return;
   }
   // i: index of char[] PS
   for (int i = 0; i < remain.length; i++) {
     if (i % 2 == 0) { //add a new left
       if (remain[i] > 0) {   
         cur.append(PS[i]);
         stack.offerFirst(PS[i]);
         remain[i]--;
         helper(cur, stack, remain, length, res);
         remain[i]++;
         cur.deleteCharAt(cur.length() - 1); //remove added parenthese
         stack.pollFirst();
       } 
     } else { //add a new right
       if (!stack.isEmpty() && stack.peekFirst() == PS[i - 1]) {
         cur.append(PS[i]);
         stack.pollFirst();
         remain[i]--;
         helper(cur, stack, remain, length, res);
         remain[i]++;
         cur.deleteCharAt(cur.length() - 1);
         stack.offerFirst(PS[i - 1]);
       }
     }
   }
 }