題目網址：https://leetcode.cn/problems/generate-parentheses/

題意：數字 n 代表生成括號的對數, 生成所有可能的且有效的括號組合。

Solution：

想法：利用 DFS + Backtracking

  • 當 左括號個數 < n 時, 可以加入左括號

  • 當 右括號個數 < 左括號個數 時, 可以加入右括號

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        dfs(0, 0, n);
        return res;
    }

private:
    string cur;
    vector<string> res;

    void dfs(const int left, const int right, const int n){
        if (left == n && right == n) {
            res.emplace_back(cur);
            return;
        }

        if (left < n) {
            cur += '(';
            dfs(left + 1, right, n);
            cur.pop_back();
        }

        if (right < left) {
            cur += ')';
            dfs(left, right + 1, n);
            cur.pop_back();
        }
    }
};
  • time：$O(\dfrac{4^n}{n \sqrt n})$ ➔ 取決於第 n 個 Catalan number $\dfrac{1}{n+1} \left(\begin{array}{ccc} 2n \\ n \ \end{array} \right)$, 近似於 $O(\dfrac{4^n}{n \sqrt n})$
    證明網址(不重要)
  • space：$O(n)$ ➔ 撇除要返回的 array res, 取決於遞迴深度, 遞迴最大深度為 2n