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

/**
 * @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))).