October 14th, 2012 | 
该问题来自于《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的解法，以后有时间有兴趣的话再研究吧。
» 转载请注明来源及链接：未来代码研究所
Posted in 
Tags: 