Generate Parentheses

Problem:

Given a positive integer n, generate combination of all possible well-formed parentheses with n pairs.

For example, when n = 3, the result is:

[
  "()(())",
  "((()))",
  "(())()",
  "(()())",
  "()()()"
]

Solution:

We need to enumerate all the possible combinations, that suggests recursive and backtracking. For backtracking, we need a few elements for the recursive call: an accumulator for the target string, a tracker to tell when to register result or return. Here is one of many possible designs. We can use a string to store the result, use an integer for open parentheses remains, another integer for close parentheses remains. The return condition is when we consumed both open and close parentheses (valid), the remaining open parentheses are more than close parentheses (invalid). The recursive logic is: if we have open parentheses, try it. After try open parentheses, try close parentheses instead.

class Solution {
  public static void main(String...args) {
    int n = 3;
    backtrack(3, 3, "");
  }
  public static void backtrack(int open, int close, String result) {
    if(open == 0 && close == 0) {
      System.out.println(result);
      return;
    }
    if(close < open) {
      return;
    }
    if(open > 0) {
      backtrack(open -  1, close, result + "(");
    }
    backtrack(open, close - 1, result + ")");
  }
  /*
  backtrack(3, 3, "");
  3, 3, ""
     2, 3, "("
        1, 3, "(("
           0, 3, "((("
              0, 2, "((()"
                 0, 1, "((())"
                    0 0 "((()))" return
           1, 2, "(()"
              0, 2, "(()("
                 0, 1, "(()()"
                    0. 0, "(()())" return
              1, 1, "(())"
                 0, 1, "(())("
                 0, 0, "(())()"  return
              1, 0, "(()))"  invalid 
        2, 2, "()"
           1, 2, "()("
              0, 2, "()(("
                 0, 1, "()(()"
                    0, 0, "()(())" return
              1, 1, "()()"
                 0, 1, "()()("
                    0, 0, "()()()" return
                 1, 0, "()())" invalid
           2, 1, "())" invalid 
     3, 2, ")" invalid         
  */
}

Time complexity O(4^n/sqrt(n)). Space complexity O(4^n/sqrt(n)). According to n-th Catalan number.