careercup-递归和动态规划 9.6

9.6 实现一种算法，打印n对括号的全部有效组合（即左右括号正确配对）。

类似leetcode：Generate Parentheses

解法：

从头开始构造字符串，从而避免出现重复字符串。在这个解法中，逐一加入左括号和右括号，只有字符串仍然有效。每次递归调用，都会有个索引指向字符串的某个字符。我们需要选择左括号或右括号，那么，何时可以用左括号，何时可以用右括号呢？

左括号：只有左括号还没有用完，就可以插入左括号

右括号：只有不造成语法错误，就可以插入右括号。何时出现语法错误？如果右括号比左括号还多，就会出现语法错误。

因此，我们只需记录允许插入的左右括号数目。如果还有左括号可用，就插入一个左括号然后递归。如果右括号比左括号好多（也就是使用中的左括号比右括号还多），就插入一个右括号然后递归。

C++实现代码：

#include<iostream>
#include<vector>
#include<string>
using namespace std;

void helper(int left,int right,vector<string> &res,string &str)
{
    if(left>right)
        return;
    if(left==0&&right==0)
    {
        res.push_back(str);
        return;
    }
    if(left>0)
    {
        str+='(';
        helper(left-1,right,res,str);
        str.pop_back();
    }
    if(right>0)
    {
        str+=')';
        helper(left,right-1,res,str);
        str.pop_back();
    }
}
vector<string> generateParens(int n)
{
    if(n<=0)
        return vector<string>();
    vector<string> ret;
    string path;
    helper(n,n,ret,path);
    return ret;

}

int main()
{
    vector<string> res=generateParens(3);
    for(auto a:res)
        cout<<a<<endl;
}