leetcode-回溯-22

题面

重点

见源代码注释部分

源代码（重点在注释部分）

初级阶段

class Solution {
public:
    //用递归实现回溯算法
    //这里的&就是把C中的指针简化一下
    void  digui(string & temp,int n,vector & result){
        if(temp.size() == 2*n){
            if(valid(temp)){
                result.push_back(temp);
            }
            return;
        }
        //“有进必有出”
        temp.push_back('(');
        digui(temp,n,result);
        temp.pop_back();
        temp.push_back(')');
        digui(temp,n,result);
        temp.pop_back();

    }
    //判断当前的括号序列是否合法
    bool valid(string temp){
        int len = temp.size();
        int balance = 0;
        //遇到左括号，balance++；遇到右括号，balance--
        for(int i=0; i generateParenthesis(int n) {
        vector result;
        string temp;
        digui(temp,n,result);
        return result;

    }
};

高级阶段

class Solution {
public:
    //用递归实现回溯算法
    //这里的&就是把C中的指针简化一下
    //left表示当前插入的左括号的数量，right表示当前插入的右括号的数量
    void degui2(vector & result,string & temp,int left,int right,int n){
        if(temp.size() == 2*n){
            result.push_back(temp);
            return;
        }
        //left generateParenthesis(int n) {
        vector result;
        string temp;
        degui2(result,temp,0,0,n);
        return result;
    }
};