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

[douglas1997]

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

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

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

[jmc891205]

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

[rockjike]

https://github.com/azl397985856/leetcode/blob/master/problems/22.GenerateParentheses.md

[douglas1997]

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

[douglas1997]

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

[keith1126]

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

[Yvette]

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

[leishi1313]

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

[aguesuka]

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

[aguesuka]

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

[jmc891205]

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

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

[jmc891205]

@aguesuka 学习了👍