22. Generate Parentheses

Problem

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

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

Solution (Java)

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

    private List<String> generate(StringBuilder sb, List<String> str, int open, int close) {
        if (open == 0 && close == 0) {
            str.add(sb.toString());
            return str;
        }
        if (open > 0) {
            sb.append('(');
            generate(sb, str, open - 1, close);
            sb.deleteCharAt(sb.length() - 1);
        }
        if (close > 0 && open < close) {
            sb.append(')');
            generate(sb, str, open, close - 1);
            sb.deleteCharAt(sb.length() - 1);
        }
        return str;
    }
}

Solution (Javascript)

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
  var res = [];
  if (n < 1) return res;
  generate(res, '', n, n);
  return res;
};

var generate = function (res, str, ll, rr) {
  if (ll || rr) {
    if (rr > ll) generate(res, str + ')', ll, rr - 1);
    if (ll) generate(res, str + '(', ll - 1, rr);
  } else {
    res.push(str);
  }
};

Explain:

每一层最多两种情况：

1. 右括号比左括号多，加右括号
2. 还有左括号，加左括号

Complexity:

• Time complexity : O((4^n)/(n^(-1))).
• Space complexity : O((4^n)/(n^(-1))).