leetcode 22 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

提示：

• 1 <= n <= 8   //这种用例很可能就是递归

代码：

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        string s = "";
        f(n,ans,s,0,0,0);
        return ans;
    }
//掌握全局思路做
    void f(int n,vector<string>&ans,string s,int i,int lnum,int rnum){
       //i 下标位置  lnum 左括号数   rnum 有括号数   n 括号对数
       //只有正确的情况才会加一个'(' 或')'
        if(i == 2*n){    //把握好边界条件，生够括号就结束
            ans.push_back(s);
            return;
        }
            
        if(i == 0){   //第一个位置只能是 '('
            s+='(';
            lnum++;
            f(n,ans,s,i+1,lnum,rnum);
        }
        else if(i == 2*n-1){  //最后一个位置只能是')'
            s+=')';
            rnum++;
            f(n,ans,s,i+1,lnum,rnum);
            
        }else{   //中间位置
            if(lnum == n){  //如果'('够n个  剩余全加')'
                s+=')';
                rnum++;
                f(n,ans,s,i+1,lnum,rnum);
            }else{  //中间位置

                s+='(';   //只要'('不够n个就可以加'('，中间任意位置都可以加
                lnum++;
                f(n,ans,s,i+1,lnum,rnum);

                lnum--;  //虽然传的不是引用，但这里是同层调用，也需要回溯到原来的样子
                
                if(rnum < lnum){  //如果')'个数小于'('的，这个位置还可以加')',如果已经等于了，那是只能加'('的。不可能出现大于，因为是按正确情况走的。
                    s = s.substr(0,s.size()-1);
                    s+=')';
                    rnum++;
                    f(n,ans,s,i+1,lnum,rnum);
                }
            }
        }
        
    }
};