leecode第二十二题（括号生成）

class Solution {
public:
    void is_kuohao(vector<int> temp,int n,vector<string>& result)//检测是不是括号，如果是，就打入result
    {
        bool is_real=true;
        int sum_front=0;
        for(int i=0;i<n;i++)
        {
            if(i>0)
                sum_front+=temp[i-1];
            if(!(temp[i]<=(i+1-sum_front)))//检测条件1：所有左括号后面接的右括号，其个数不能多于前面所有左括号数目
                is_real=false;
        }
        if(temp[n-1]<1)//检测条件2：最后一个一定是右括号
            is_real=false;
        
        if(is_real)//打入result
        {
            string new_item;
            for(int i=0;i<n;i++)
            {
                new_item.push_back('(');
                for(int j=0;j<temp[i];j++)
                    new_item.push_back(')');
            }
            result.push_back(new_item);
        }
    }
    
    void baoli(int retain_vlaue,int num_all,int n,vector<string>& result,vector<int>& temp)//递归生成所有可能的组合
    {
        if(n==0)
            return;
        if(n==1)//终止条件
        {
            temp[0]=retain_vlaue;
            is_kuohao(temp,num_all,result);
            return;
        }
        
        for(int i=retain_vlaue;i>=0;i--)//递归主体
        {
            temp[n-1]=i;
            baoli(retain_vlaue-i,num_all,n-1,result,temp);
        }
        
    }
    
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        vector<int> temp(n,0);
        baoli(n,n,n,result,temp);
        return result;
    }
    
    
    
};

分析：

一开始各种想，没想到好多人推荐的居然是暴力法。。。