求大家指点一下(不用使用循环和递归都做.一种即可.这个用递归更简单些)

Question

问题:

左“{”，右”}"括号各N个，请打印出所有正确的组合，比如当N=3，{}{}{}，{}{{}}，等为正确的组合。如果写的代码是recursive，能否用iterative再写一个；反之亦然。

py实现:

def foo(output, open, close, pairs):	if open == pairs and close == pairs:		print output
	else:		if open<pairs:
			foo(output+'(', open+1, close, pairs)		if close<open:
			foo(output+')', open, close+1, pairs)

foo('', 0, 0, 3)

Answer 1

这个很容易就可以想到用回溯法来做。假设从左往右填括号。状态包括：(1) 填到第几个：int i(2) 在右边最多还能填多少个 "}"：int left(3) 还剩多少个"{"可以填：int a(4) 还剩多少个"}"可以填：int b具体策略：(1) 如果已经填完了，输出，返回（回溯）(2) 如果还有"{"可以填：填进去，递归填下一个。(3) 如果还可以填"}"并且还有"}"可以填：填进去，递归填下一个。实现的代码附在后面。至于转化成迭代的方式，任何递归都可以通过引入栈的方式来转化，只是写起来比较痛苦，看起来也比较痛苦就是了。#include&nbsp;<stdio.h>const&nbsp;int&nbsp;maxn&nbsp;=&nbsp;50;char&nbsp;x[maxn&nbsp;*&nbsp;2&nbsp;+&nbsp;1];void&nbsp;perm(int&nbsp;i,&nbsp;int&nbsp;left,&nbsp;int&nbsp;a,&nbsp;int&nbsp;b)&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(a&nbsp;==&nbsp;0&nbsp;&&&nbsp;b&nbsp;==&nbsp;0)&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;puts(x);&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(a&nbsp;>&nbsp;0)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x[i]&nbsp;=&nbsp;'{';&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;perm(i&nbsp;+&nbsp;1,&nbsp;left&nbsp;+&nbsp;1,&nbsp;a&nbsp;-&nbsp;1,&nbsp;b); &nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(b&nbsp;>&nbsp;0&nbsp;&&&nbsp;left&nbsp;>&nbsp;0)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;x[i]&nbsp;=&nbsp;'}';&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;perm(i&nbsp;+&nbsp;1,&nbsp;left&nbsp;-&nbsp;1,&nbsp;a,&nbsp;b&nbsp;-&nbsp;1); &nbsp;&nbsp;&nbsp;&nbsp;} }int&nbsp;main()&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;n&nbsp;=&nbsp;4; &nbsp;&nbsp;&nbsp;&nbsp;x&nbsp;[n&nbsp;*&nbsp;2]&nbsp;=&nbsp;0;&nbsp;&nbsp;&nbsp;&nbsp;perm(0,&nbsp;0,&nbsp;n,&nbsp;n);&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;0; }