22. Generate Parentheses

/**
 *                     (
 *        ((                        ()
 *                 (()              ()(
 *   (((      (()(     (())     ()((     ()()
 *  ((())) , (()()) , (())() , ()(()) , ()()()
 */

class Solution {
  public List<String> generateParenthesis(int n) {
    ArrayList<String> solution = new ArrayList<String>();
    generate(solution, n, n, "");
    return solution;
  }

  public void generate(List<String> solution, int open, int close, String s) {
    if(open == 0 && close == 0) {
      solution.add(s);
      return;
    }

    if(open > 0) {
      generate(solution, open - 1, close, s + "(");
    }

    if(close > 0 && open < close) {
      generate(solution, open, close - 1, s + ")");
    }
  }
}