dfs之有重复字符串的排列组合

https://leetcode.cn/problems/permutation-ii-lcci/description/

■ 题目描述

考古问题，假设以前的石碑被打碎成了很多块，每块上面都有一个或若干个字符，请你写个程序来把之前石碑上文字可能的组合全部写出来，按升序进行排列。

示例1   输入输出示例仅供调试，后台判题数据一般不包含示例

输入

3

a b c

输出

abc

acb

bac

bca

cab

cba

示例2   输入输出示例仅供调试，后台判题数据一般不包含示例

输入

3

a b a

输出

aab

aba

baa

/*** Note: The returned array must be malloced, assume caller calls free().*/void Swap(char *a, char *b)
{char t;t = *a;*a = *b;*b = t;
}/* 进行递归的函数 */
int DFS(char *temp, int len, int k, char **res, int *returnSize)
{// k是当前要插入的位置的下表，k之前的都已经插入完成了char used[27]; //表示出现过的字母int j;int userdi = 0;//递归结束的条件，大循环下表来到最后一个元素，无需操作if (k >= len - 1) {strcpy(res[(*returnSize)++], temp);return 0;}for (int i = k; i < len; i++) {if (userdi == 0) {used[userdi++] = temp[i];} else {for (j = 0; j < userdi; j++) {if (used[j] ==  temp[i]) {break;}}if (j >= userdi) {used[userdi++] = temp[i];} else {continue;}}Swap(&temp[i], &temp[k]);DFS(temp, len, k + 1, res, returnSize);Swap(&temp[i], &temp[k]);}return 0;
}char** permutation(char* S, int* returnSize){char **res;int resNum, len = strlen(S);int i, j, k;char *temp = malloc(sizeof(char) * (len + 2));strcpy(temp, S);res = malloc(sizeof(char *) * 1000);for (i = 0; i < 1000; i++) {res[i] = malloc(sizeof(char) * len + 1);}resNum = 0;k = 0;*returnSize = 0;DFS(temp, len, k, res, returnSize);return res;
}