leetcode22. 括号生成

分析

回溯时当左括号比右括号多时才可以加入')'，否则就加入'('。

class Solution {
public:
    vector<string> ans;
    string path;
    void dfs(int open,int close,int n){
        if(path.size()==n*2){
            string s;
            for(auto c:path)s+=c;
            ans.push_back(s);
        }
        if(open<n){
            path.push_back('(');
            dfs(open+1,close,n);
            path.pop_back();
        }
        if(open>close){
            path.push_back(')');
            dfs(open,close+1,n);
            path.pop_back();
        }

    }
    vector<string> generateParenthesis(int n) {
        dfs(0,0,n);
        return ans;
    }
};