ABC字符串,该怎么处理

ABC字符串
求一个算法ABC三个字母，AB不能相邻，C不能在两端出现，要求输入一个整数，输出共有多少种字符串？
例如：输入 1，共有两种：A B;当输入2，共有两种 :AA BB；当输入3，共有6种：AAA BBB 
ACA BCA ACB BCB

[解决办法]
全排列组合，不符合条件的字符串不输出，过滤掉。
[解决办法]
回溯法弄出所有的串，然后去掉不符合条件的串
[解决办法]
http://www.cnblogs.com/nokiaguy/archive/2008/05/11/1191914.html
[解决办法]
组合排列。
[解决办法]
for example

C/C++ code

static void parade(int num){    int *dig = (int*)malloc(sizeof(int) * num);    int i, j, count=0;    for (i=0; i<num; i++)        dig[i] = 0;    while(dig[0] < 2)    {        j = 0;        if (dig[num-1] != 2)        {            for (i=1; i<num; i++)            {                if ((dig[i-1]==0 && dig[i]==1) ||                     (dig[i-1]==1 && dig[i]==0))                    break;            }            j = (i == num) ? 1 : 0;            if (j)            {                for (i=0; i<num; i++)                    cout<<(char)('A'+dig[i]);                cout<<endl;                count++;            }        }        dig[num-1]++;        for (i=num-1; i>0; i--)        {            if (dig[i] < 3)                break;            dig[i-1]++;            dig[i] = 0;        }    }    cout<<"--------------------"<<endl;    cout<<"total: "<<count<<endl;    free(dig);}int _tmain(int argc, _TCHAR* argv[]){    int num;    cout<<"please input a num:";    cin >> num;    parade(num);    system("pause");}
[解决办法]
探讨

求解释啊 不懂啊