该问题来自于《Cracking the Coding Interview 5th edition》练习题9.6。原题描述如下:“Implement an algorithm to print all valid (i.e., properly opened and closed) combinations of n-pairs of parentheses.”
该问题是典型的递归问题,有点类似于全排列算法,不同之处在于这里含有重复元素,而且需要验证左右的括号是否正确匹配。我在这里给出的代码和书上给的第二种解法原理基本相同,不过我觉得我的代码更简洁和易懂一点,所以发出来以备有需要的人参考。
#include <stdio.h>
#define N 3
char str[N * 2 + 1];
void foo(int left, int leftopen, int depth)
{
int index = depth - 1;
if (depth == N * 2)
{
str[index] = ')';
puts(str);
return;
}
else
{
if (left < N)
{
str[index] = '(';
foo(left+1, leftopen+1, depth+1);
}
if (leftopen > 0)
{
str[index] = ')';
foo(left, leftopen-1, depth+1);
}
}
}
int main()
{
str[0] = '(';
str[N * 2] = '\0';
foo(1, 1, 2);
return 0;
}
#define N 3
char str[N * 2 + 1];
void foo(int left, int leftopen, int depth)
{
int index = depth - 1;
if (depth == N * 2)
{
str[index] = ')';
puts(str);
return;
}
else
{
if (left < N)
{
str[index] = '(';
foo(left+1, leftopen+1, depth+1);
}
if (leftopen > 0)
{
str[index] = ')';
foo(left, leftopen-1, depth+1);
}
}
}
int main()
{
str[0] = '(';
str[N * 2] = '\0';
foo(1, 1, 2);
return 0;
}
程序使用Visual Studio 2010验证通过。
另外这道题似乎还有使用bit map的解法,以后有时间有兴趣的话再研究吧。
» 转载请注明来源及链接:未来代码研究所