企业面试时遇到python括号匹配笔面问题求解

问题:

左“{”，右”}"括号各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)

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

玩蛇网文章，转载请注明出处和文章网址：https://www.iplaypy.com/wenda/wd20427.html