首页 > 代码库 > careercup-递归和动态规划 9.6

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;}

 

careercup-递归和动态规划 9.6