给定一个可包含重复字母的序列,按任意顺序返回所有不重复的全排 列。

思路：
与“全排列”问题类似，只是需要在生成全排列的过程中，去除重复的情况。可以使用回溯算法，在生成每个排列时进行判断。具体步骤如下：

1. 首先对原序列进行排序，方便后续去重判断。
2. 使用一个布尔数组visited记录每个元素是否被访问过，初始化为false。
3. 在回溯函数中，对于每个位置i，枚举可填入的字符。
4. 若该字符已被填过，则跳过；若未填过，则填入，并将visited对应位置设为true。
5. 递归到下一位，直到填完所有位置，将当前排列加入结果集。
6. 在回溯时，需要将当前填入的字符恢复为未填状态，将visited对应位置设为false，避免重复计算。

代码：

相关问题

用C语言写该题目：给定一个可包含重复字母的序列，按任意顺序返回所有不重复的全排 列。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 100

void dfs(char *s, int len, int *used, char *path, int depth, char **res, int *resSize) {
    if (depth == len) {
        res[*resSize] = (char *)malloc(sizeof(char) * (len + 1));
        strcpy(res[*resSize], path);
        (*resSize)++;
        return;
    }

    for (int i = 0; i < len; i++) {
        if (used[i] || (i > 0 && s[i] == s[i - 1] && !used[i - 1])) {
            continue;
        }
        path[depth] = s[i];
        used[i] = 1;
        dfs(s, len, used, path, depth + 1, res, resSize);
        used[i] = 0;
    }
}

char **permuteUnique(char *s, int *returnSize) {
    int len = strlen(s);
    int used[MAX_N] = {0};
    char path[MAX_N] = {0};
    char **res = (char **)malloc(sizeof(char *) * MAX_N * MAX_N);
    *returnSize = 0;

    // 排序是为了剪枝
    qsort(s, len, sizeof(char), strcmp);
    dfs(s, len, used, path, 0, res, returnSize);

    return res;
}

int main() {
    char *s = "abc";
    int returnSize;

    char **res = permuteUnique(s, &returnSize);

    for (int i = 0; i < returnSize; i++) {
        printf("%s\n", res[i]);
    }

    return 0;
}