生成n对括号的所有合法排列-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

生成n对括号的所有合法排列

简介:

实例

n = 3,所有的合法序列

((()))  (()()) (())() ()(()) ()()()     

思路

针对一个长度为2n的合法排列,第1到2n个位置都满足如下规则

1
左括号的个数≥右括号的个数

所以,我们就可以按照这个规则去打印括号

假设在位置k我们还剩余left个左括号和right个右括号

  • 如果left和right均为零,则说明我们已经完成一个合法排列,可以将其打印出来
  • 如果left>0,打印左括号
  • 如果right>0 并且 right>left 打印右括号

针对n=2,问题的解空间如下:

参考代码

复制代码
vector<string> generateParenthesis(int n) 
{
    vector<string> ans;
    generate(n, n, "", ans);
    return ans;
}
void generate(int leftNum, int rightNum, string s, vector<string> &result)  
{  
    if(leftNum == 0 && rightNum == 0)  
    {  
        result.push_back(s);  
    }  
    if(leftNum > 0)  
    {  
        generate(leftNum-1, rightNum, s+'(', result);  
    }  
    if(rightNum > 0 && leftNum < rightNum)  
    {  
        generate(leftNum, rightNum-1, s+')', result);  
    }  
} 
复制代码

扩展

该问题和《编程之美》的买票找零问题一样:2n个人排队买票,其中n个人持50元,n个人持100元。每张票50元,且一人只买一张票。初始时售票处没有零钱找零。请问这2n个人一共有多少种排队顺序,不至于使售票处找不开钱?

可以把50块钱看成(,100块钱看成)。只有(始终大于等于)才可以找开钱。

结论

 





本文转自jihite博客园博客,原文链接:http://www.cnblogs.com/kaituorensheng/p/3836757.html,如需转载请自行联系原作者


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章
最新文章
相关文章