华为笔试题:括号的排列组合

摘要：给定N个括号(N为偶数),求出所有正确的组合.

基本思路:

[1]最简单的思路就是进行递归的计算,每一次递归有2个循环(判断该次括号是”(“还是”)”)。但是这种方法是在是太笨了,需要计算2^N，而且递归调用的次数太多.

[2]稍微好一点的思路是将括号视作二进制序列,左括号时候0，右括号是1.然后从1到2^N进行循环,这样避免了递归,但是时间界并没有改变.

[3]再好一点的办法是,考虑到正确的组合左右括号的数量是相等的.那么对于括号序列对应的二进制序列,它的值应该是2^a + 2^b + 2^c + 。。。+2^i(其中每一个幂的值都介于0到N-1)之间.这样所获得的括号序列一定是左右括号数量相等的.时间界则变成了 c(n/2n) ,这是一个很大的提升.

[4]现在要考虑的是如何求解进行排列.每次我们选取一个位置将该处置为1,并记录当前的位置为i,然后进行下一次递归的调用获取下一个位置i2,i2一定在i的后面.设已经置为1的位置有x个,那么还有N/2 - x个位置（包括本次的i2）需要置为1。因此Bit2的取值范围是(i1+1 ≤ i2 ≤ N/2+x),通过这样的方式最后得到十进制值转化为二进制然后转化为括号(当然可以在递归的过程中直接赋值括号,更加简便，这次只是为了贯彻二进制的思路).

#include "stdafx.h"
#include "stdlib.h"
#include "math.h"
#include "string.h"
#define N 4


void print(char *s)
{
    int static times = ;
    int i = ;
    printf(" \n组合%d ：",times++);
    while(i<=*N-)
    {
        printf("%c",s[i] == '0'?'(':')');
        i++;
    }
}
void check(char *s)
{
    int number = ,number1 = ,i;

     for( i = ;i<=*N-;i++)
    {
        if(s[i] == '0')
            number++;
        else
            number1++;
        if(number < number1)
            break;
    }
    if(i == *N)
        print(s);
}

void GetNumber(int number,int PrePosition,int bits)
{
    int length;
    char *temp = (char*)malloc(sizeof(char)*2*N);
    char *s = (char*)malloc(sizeof(char)*2*N);
    memset(s,'0',sizeof(char)*2*N);
    if(bits != N)
    {
    for(int i = PrePosition + ;i<=bits+N;i++)
                GetNumber(number+(<<i),i,bits+);
    }
    else
    {
                itoa(number,temp,);
                length = strlen(temp);
                memcpy(s+(*N - length),temp,sizeof(char)*length);
                s[*N] = '\0';
                check(s);
    }
}
int _tmain(int argc, _TCHAR* argv[])
{ 

    GetNumber(,-,);
    return ;
}