救救孩子吧！如何用循环写出 n 对括号的所有组合情况？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

V2EX 提问指南

这是一个创建于 1621 天前的主题，其中的信息可能已经有所发展或是发生改变。

n 对括号(e.g. n=2, "()()"), 所有组合["(())", "()()", "())(", ")()(", ")(()", "))(("]。

这个如何用循环，而不是用递归实现呢？想了一晚上了，请大神赐教！

想法来源于 LeetCode 22 题，找到合理的括号，第一种暴力解法是看作二叉树然后递归遍历，但是循环怎么写没想出来。

11 条回复 • 2020-06-08 07:14:41 +08:00

jmc891205

2020-06-07 21:43:14 +08:00 via iPhone

自己开一个栈去存当前状态就可以了

rockjike

2020-06-07 21:46:45 +08:00

douglas1997

2020-06-07 21:59:15 +08:00

@rockjike 不是呀，是用循环去实现所有的可能性，不是原题。

douglas1997

2020-06-07 21:59:46 +08:00

@jmc891205 大神可否写一个伪代码我学习一下= =

keith1126

2020-06-07 22:01:39 +08:00

递归本质上就是循环+栈啊，不仅仅是这道题，理论上是可以把所有递归用栈改写为非递归形式，所以你可以去了解一下~

Yvette

2020-06-07 23:11:00 +08:00

一个方法是先把递归改成尾递归，然后把尾递归的结果单独提出来，就可以很直观地改写成迭代写法了

leishi1313

2020-06-08 04:29:21 +08:00 via Android

跟括号有什么关系，不就是个全排列+去重嘛

aguesuka

2020-06-08 07:06:18 +08:00 via Android

不需要栈
for(int i=0;i< (i<<n);i++){
如果 i 的第 m 位是 0 就是左括号，否则就是右括号
}

aguesuka

2020-06-08 07:07:54 +08:00 via Android

ps 上面这个算法是针对主楼的，不是 leetcode 的

jmc891205

2020-06-08 07:14:19 +08:00 via iPhone

@douglas1997 我手机回的，写代码什么的不太方便。你网上随便搜下递归改写成迭代，很多人都讲过的。基本上思路就是自己维护一个栈来模拟函数栈。

回到这个题，暴力解法太慢了，AC 不了。

jmc891205

2020-06-08 07:14:41 +08:00 via iPhone

@aguesuka 学习了👍