22.Generate Parentheses

Tags: Medium Backtracking String

Links: https://leetcode.com/problems/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:

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

---

class Solution {
public:
    vector<string> res;
    void solve(int left, int right, int n, string tmp)
    {
        if (left == n && right == n) {
            res.push_back(tmp);
            return;
        }

        if (left < n) 
            solve(left + 1, right, n, tmp + "(");

        if (right < left)
            solve(left, right + 1, n, tmp + ")");
    }

    vector<string> generateParenthesis(int n) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        solve(0, 0, n, "");
        return res;
    }
};

时间复杂度就是卡特兰数的求法。

递归的思路：

• 每次可以放置左括号的条件是当前左括号的数目不超过 n。
• 每次可以放置右括号的条件是当前右括号的数目不超过左括号的数目。

时间复杂度是第n个卡特兰数，$\frac{n}{n+1} C_{2n}^n$，为$O(\frac{4^n}{\sqrt{n}})$。