class Solution {
public:
    vector<string> generateParenthesis(int n) {
        string s;
        for(int i=0;i<n*2;i++) s=s+" ";
        
        vector<string> result;
        int left=n;
        int right=n;
        gen(result,s,left,right,0);
        return result;
    }
    void gen(vector<string>& result,string& s,int left,int right,int step)
    {
        if(left>right) return;
        if(left==0 && right==0)
        {
            result.push_back(s);
            return;
        }
        if(left>0)
        {
            s[step]=‘(‘;
            gen(result,s,left-1,right,step+1);
        }
        if(right>0)
        {
            s[step]=‘)‘;
            gen(result,s,left,right-1,step+1);
        }
    }
};