！！！题解 | 括号生成 这个思路真的非常的妙，从策略上就根本不会进入不合法的路径，

#include <string>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串vector
     */
    vector<string> generateParenthesis(int n) {
        // write code here
        //莫要着急，先画排列树
        vector<string> res;
        string path;
        int left=0;
        int right=0;
        if(n==0)return res;
        func(n, path, res, left, right);
        return res;
    }
    //是不是和数字的全排列是大差不差的只不过剪枝条件不一样而已。
    /*差不多但是也不太一样。因为这个地方剪枝是重中之重，
    而剪枝有一个神来之笔，就是括号匹配是一个“欠债还钱”的思路。
    （ 相当于欠债 ，）相当于还钱。一个（ 肯定要与一个 ）进行匹配，
    但是如果）的数量大于了（，那么就注定这个组合是不合法的。
    所以要保证（的数量始终要比）的数量要多。欠了债才能还钱，
    而这个时候不管 ）被放置在哪个位置组合都是合法的
    */
    void func(int n,string& path,vector<string>& res,int left,int right){
        if(path.size()==2*n){
            res.push_back(path);
            return;
        }//还要注意（的数量和）的数量都要小于n
        /*这和数字的全组合不太一样。那个是有N种不同的选择，但是在这里每一个分支只有两种选择，
        要么是（要么是），所以没有必要用for循环，只用两个if语句就可以了。
        然后这里根据上面的分析需要保证的是（的数量一定要比）的数量要多，所以这个if条件的顺序放在上面作为优先选择，所以就会优先放入（，直到（放完了之后就可以往下走，开始放入）。
        然后如果数量达到就收集这个路径，并回溯，但是因为放入）是最后一种选择，所以它就会直接退出这一层，进入下一层还是会优先放入（
        */
        /*
        优先放入 (：是因为代码写在上面，且一旦进入递归就会忽略下面的代码。
        并且也保证了所生成的组合一定是合法的，虽然它并没有显式地进行剪枝，
        但是因为这个机制会让他根本不会进入那些不合法的路径，效率反而更高。
收集所有结果：是因为递归结束后会回溯（pop），回到分叉口，继续尝试第二种可能性（放 )）。
它会把这棵决策树的每一条枝丫都走一遍*/
        if(left<n){
            path+="(";
            func(n, path, res, left+1, right);
            path.pop_back();
        }
        if(right<n&&left>right){
            path+=")";
            func(n, path, res, left, right+1);
            path.pop_back();
        }

    }
};