LeetCode 22. Generate Parentheses [Medium] [C++] 解題筆記

這題給定 n 組括弧，要我們求出 n 組括弧所能形成的所有合法組合。

EX:

        n = 3,

    [

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

想法:

        基本上這就是一個 dfs backtracking 的問題，就單純依照 左括弧，右括弧分別列舉即可，需要

注意的是，因為一個括弧的表示式要合法的話當前左括弧個數必定 >= 右括弧個數，因此當列舉到左括弧 < 右括弧

的情況時就可以返回了，可以稍微做一下剪枝。

完整程式碼:

class Solution {
public:
    vector<string> res;
    void dfs(int n, int left, int right, string& cur) {
        if (right > left) { return; }
        if (left == n && right == n) {
            res.emplace_back(cur);
            return; 
        }
        if (left < n) {
            cur.push_back('(');
            dfs(n, left + 1, right, cur);
            cur.pop_back();
        }
        if (right < n) {
            cur.push_back(')');
            dfs(n, left, right + 1, cur);
            cur.pop_back();
        }
    }
    vector<string> generateParenthesis(int n) {
        string cur = "";
        dfs(n, 0, 0, cur);
        return res;
    }
};