华为机试

考古学家发现了一个石碑，可惜其已经断成了多段，原地发现n个断口整齐的石碑碎片，为了破解石碑的内容，考古学家希望有程序可以帮忙计算复原后的石碑文字的组合数。

输入描述：第一行输入n，表示石碑碎片的个数第二行依次输入石碑碎片上的文字内容s，共有n组

输出描述：输出石碑文字的组合(按升序排列)，行末无多余空格

示例1：输入3 a b c

输出abc acb bac bca cab cba

说明abc三个字母的所有组合，按照字典序升序排列输出

示例2：输入3a b a

输出aab aba baa说明可能组合有“aab”“aba”“baa”

示例3：输入3a b ab

输出aabba babab babaa bbaba

备注：如果存在石碑碎片完全相同，相同碎片间的顺序变换不影响复原后的碑文内容。

#include <stdio.h>

#include <malloc.h>

#include <string.h>

#include <stdlib.h>

const int Row = 3;

const int Col = 20;

char **S;

const int resultColunmSize = 40;

char** result;

int resultCount = 0;

char* path;

int pathCount = 0;

//S[i]那一行的字符串是否已经使用

bool isUsed[Row];

void init()

{

S = (char**)malloc(sizeof(char*)* Row);

result = (char**)malloc(sizeof(char*)* Row*Col);

for (int i = 0; i < Row; i++)

{

S[i] = (char*)malloc(sizeof(char)*Col);

memset(S[i], '\0', 20);

isUsed[i] = false;

}

for (size_t i = 0; i < Row*Col; i++)

{

result[i] = (char*)malloc(sizeof(char)* Col);

memset(result[i], '\0', 20);

}

path = (char*)malloc(sizeof(char)* Col);

memset(path, '\0', resultColunmSize);

S[0][0] = 'a';

S[1][0] = 'a';

S[1][1] = 'c';

S[2][0] = 'b';

}

void put()

{

bool isIncluded = false;

for (size_t i = 0; i < resultCount; i++)

{

if (0 == strcmp(result[i], path))

{

isIncluded = true;

}

}

if (!isIncluded)

{

strcpy(result[resultCount++], path);

return;

}

}

void back(bool isUsed[])

{

if (pathCount == Row)

{

//去重

put();

resultCount++;

return;

}

for (int i = 0; i < Row; i++)

{

if (isUsed[i] == false)

{

pathCount++;

isUsed[i] = true;

//把S[i]里的字符串追加在Path后面

char* temp = (char*)malloc(sizeof(char)* Col);

memset(temp, '\0', Col);

strcpy(temp, path);

strcat(path, S[i]);

back(isUsed);

isUsed[i] = false;

path = temp;

pathCount--;

}

}

}

int cmp(const void*a, const void*b)

{

const char * pa = *(const char**)a;

const char * pb = *(const char**)b;

return strcmp(pa, pb);

}

void sortByDirectory()

{

qsort(result, resultCount, sizeof(char*), cmp);

}

void printfResult()

{

for (int i = 0; i < resultCount; i++)

{

printf("%s", result[i]);

printf("\n");

}

}

int main()

{

init();

bool isUsed[] = { false, false, false };

back(isUsed);

printfResult();

sortByDirectory();

printfResult();

return 0;

}