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

时间：2022-07-10 19:13:38

实例

n = 3，所有的合法序列

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

思路

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

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

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

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

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

针对n=2，问题的解空间如下：

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

参考代码

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 ==  && rightNum == )

    {

        result.push_back(s);

    }

    if(leftNum > )

    {

        generate(leftNum-, rightNum, s+'(', result);

    }

    if(rightNum >  && leftNum < rightNum)

    {

        generate(leftNum, rightNum-, s+')', result);

    }

}

扩展

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

可以把50块钱看成（，100块钱看成）。只有（始终大于等于）才可以找开钱。

结论

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

参考

http://blog.csdn.net/yutianzuijin/article/details/13161721

相关文章