華為筆試題:括号的排列組合

摘要：給定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 ;
}