22.括号生成

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

思路

一开始考虑的是长度为2n的数组，插空放左括号
但是没什么特别好的实现思路，所以看了他人代码
网上的都是使用递归，于是我也尝试了递归的方法

仍然是使用tmp+'x' 的方法，方便递归返回时删去末尾

具体代码

此处需要注意，传入的参数list需要取地址，不然的话无法存到最终结果中
void recursive(int left, int right, string tmp, vector<string>& list){
    //如果右括号全部用完，则字符串已完成 
    if(!right){
        list.push_back(tmp);
        return;
    }
    //如果左括号已全部用完，则只能添加右括号 
    if(!left){
        recursive(left, right - 1, tmp + ')', list);
    }
    else{
        //采用tmp+的方式，方便返回时删去末尾
        //第一种可能，添加左括号 
        recursive(left - 1, right, tmp + '(', list);
        
        //第二种可能，情况允许，添加右括号 
        if(left < right){   
            recursive(left, right - 1, tmp + ')', list);
        }
    }
    return;
} 
vector<string> generateParenthesis(int n) {
    vector<string> res;
    recursive(n, n, "", res);
    return res;
}