26. Generate Parentheses

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:

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

列出所有可能組合的題目通常會用到backtracking，helper function裡的n代表待加的左括號數量，m代表待加的右括號數量。

void helper(vector<string>& res, string cur, int n, int m) {
    if (n == 0 && m == 0) {
        res.push_back(cur);
        return;
    }
    if (n > 0)
        helper(res, cur + '(', n - 1, m + 1);
    if (m > 0)
        helper(res, cur +')', n, m - 1);
}
vector<string> generateParenthesis(int n) { // time: O(2^n); space: O(2^n)
    vector<string> res;
    string cur;
    helper(res, cur, n, 0);
    return res;
}