题解 | 字符串的排列

// 全局变量
char** result;
int resultSize;
int* used;

// 比较函数用于排序
int cmp(const void* a, const void* b) {
    return *(char*)a - *(char*)b;
}

// 回溯函数
void backtrack(char* s, int len, int depth, char* current) {
    if (depth == len) {
        // 找到一个排列
        result[resultSize] = (char*)malloc(sizeof(char) * (len + 1));
        strcpy(result[resultSize], current);
        resultSize++;
        return;
    }

    for (int i = 0; i < len; i++) {
        // 剪枝条件：当前字符已使用，或者当前字符与前一个相同且前一个未使用
        if (used[i] || (i > 0 && s[i] == s[i - 1] && !used[i - 1])) {
            continue;
        }

        used[i] = 1;
        current[depth] = s[i];
        backtrack(s, len, depth + 1, current);
        used[i] = 0;  // 回溯
    }
}

/**
 * 返回所有不重复的排列
 * @param s: 输入字符串
 * @param returnSize: 返回数组的大小
 * @return: 所有排列的数组
 */
char** Permutation(char* s, int* returnSize) {
    int len = strlen(s);

    // 计算最大可能排列数：len! / (重复字符的阶乘)
    // 先简单分配一个较大的空间
    int maxSize = 1;
    for (int i = 2; i <= len; i++) {
        maxSize *= i;
    }

    // 分配内存
    result = (char**)malloc(sizeof(char*) * maxSize);
    used = (int*)calloc(len, sizeof(int));
    char* current = (char*)malloc(sizeof(char) * (len + 1));
    current[len] = '\0';

    // 先排序，让相同字符相邻
    qsort(s, len, sizeof(char), cmp);

    resultSize = 0;
    backtrack(s, len, 0, current);

    *returnSize = resultSize;
    free(current);
    free(used);
    return result;
}