该问题来自于《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;
}

程序使用Visual Studio 2010验证通过。

另外这道题似乎还有使用bit map的解法,以后有时间有兴趣的话再研究吧。

» 转载请注明来源及链接:未来代码研究所

Related Posts:

Leave a Reply

World Line
Time Machine
Online Tools