leetcode 22 括号生成

思路：看起来比较难
关键：必须满足任意时刻左括号数目大于等于右括号个数
过程：

1. dfs广度搜索，从0号开始搜索，left代表左括号个数，right表示右括号个数
2. dfs中若左右括号都等于n，则表示找到一个符合要求的字符串
   只要满足left<n，则可以添加做括号
   满足left>right，则可以添加右括号
   若left<right则剪枝

class Solution {
public:
    vector<string> ans;
    void dfs(string & s,int x,int n,int left,int right)
    {//深度搜索
        if(left==n && right ==n)
        {//符合要求
            ans.push_back(s);
            return ;
        }
        if(left<right)//剪枝
            return;
        if(left<n)
        {//增加左括号
            s[x]='(';
            dfs(s,x+1,n,left+1,right);
        }
        if(right<left)
        {//增加右括号
            s[x]=')';
            dfs(s,x+1,n,left,right+1);
        }
    }
    vector<string> generateParenthesis(int n) {
        string s(2*n,'\0');
        dfs(s,0,n,0,0);
        return ans;
    }
};