LeetCode #22：Generate Parentheses(括号生成)

题目描述

注意到 1 <= n <= 8，用回溯法进行 dfs 即可解决问题。注意添置左右括号的条件——添加后必须有可能在后续的处理中构成合法的括号排列，画一棵递归树就非常清楚了。

class Solution {
public:
    vector<string> generateParenthesis(int n) {

        this->n = n;
        dfs("(", 1, 0);

        return res;
    }

private:
    void dfs(string s, int leftKuoCount, int rightKuoCount) {
        if(s.length() == n * 2) {
            if(leftKuoCount == rightKuoCount) res.push_back(s);
            return;
        } 

        if(leftKuoCount > rightKuoCount) {
             //进行剪枝，左括号的个数大于n时肯定不可能是合法的括号序列
            if(leftKuoCount <= n - 1) dfs(s + "(", leftKuoCount + 1, rightKuoCount); 
            dfs(s + ")", leftKuoCount, rightKuoCount + 1);
        } else if(leftKuoCount == rightKuoCount) {
            dfs(s + "(", leftKuoCount + 1, rightKuoCount);
        }
        
    }

    vector<string> res;
    int n;
};