22. Generate Parentheses

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        if (n == 0)
            return res;
        dfs(0, 0, n, ""); //从左右都为0开始
        return res;
    }

    vector<string> res;
    void dfs(int l, int r, int n, string cur) {
        if (l == n && r == n) {
            res.push_back(cur);
            return;
        }
        if (l < n)     //当左括号出现次数 <n 时，就可以放置新的左括号
            dfs(l + 1, r, n, cur + "(");//此时填左括号

        if (r < l)     //当右括号出现次数小于左括号出现次数时，就可以放置新的右括号。
            dfs(l, r + 1, n, cur + ")");//此时填右括号
    }
 
};
//当左括号出现次数 <n 时，就可以放置新的左括号。当右括号出现次数小于左括号出现次数时，就可以放置新的右括号。