前言

个人推荐在牛客网刷题(点击可以跳转)，它登陆后会保存刷题记录进度，重新登录时写过的题目代码不会丢失。
个人刷题练习系列专栏：个人CSDN牛客刷题专栏。题目来自：牛客/题库 / 在线编程 / 剑指offer：

问题描述：

输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。
例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。
数据范围：n<10
要求：空间复杂度 O(n!)，时间复杂度 O(n!)获取此时栈中最小元素==>返回-1


---
# 举例：
```c
//示例1：
//输入：
"ab"
//返回值：
["ab","ba"]
//说明：返回["ba","ab"]也是正确的  
//=======================
//示例2：
//输入：
"aab"
//返回值：
["aab","aba","baa"]
//=======================
//示例3：
//输入：
"abc"
//返回值：
["abc","acb","bac","bca","cab","cba"]
//=======================
//示例4：
//输入：
""
//返回值：
[""]

解法思路：

1.解题思路：还是以具体例子思考：从最简单的出发：一个字符：a，只有一种排列方式；两个字符：ab，排列方式有 ab，ba；三个字符，cab，由于 ab有两种排列方式 c这个字符可以与a b这两个字符任意调换位置。因此有 cab acb bac cba bca abc；以此类推，假设一个较长的字符串：abcdabc，那么可以考虑字符 a + bcdabc之间的组合。只需要确定了bcdabc的全排列后，那么替换a到这些位置即可，也就是a bcdabc的全排列就简化成了 bcdabc的全排列，以此类推，递归解决所有问题。
2.重点：如何去除全排列中的重复序列呢？比如说 aabb，同样的考虑a+abb递归解决，但是当a和a替换位置是无效的，同样的 a和第一个b替换以及a和第二个b替换也是等价的。因此在替换之前需要再遍历一次来判断是否之前已经出现过。

代码结果：

 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param str string字符串 * @return string字符串一维数组* @return int* returnSize 返回数组行数** C语言声明定义全局变量请加上static，防止重复定义*///两个全局变量 一个记录所有的结果 另一个判断是否重复
static int top=0;
static int flag=0;
//字符交换
int swap(char *a, char *b) {char temp = *a;*a = *b;*b = temp;return 1;
}
int perm(char **ans,char *str, int m,int n) {//到结尾了 复制一下str到ansif (m == n) {ans[top]=(char *)malloc(sizeof(char) *n);strcpy(ans[top++],str);}else {//这里就是最外层的循环 也就是将m指向的字符 分别与之后的字符依次交换for (int i = m; i < n; i++) {//这里就是去重了 在起始位置m和遍历位置i之间遍历是否已经出现相同字符 从而跳过此次遍历for(int j=m;j<i;j++){if(str[j]==str[i]){flag=1;break;}}if(flag==1){flag=0;continue;}//m和i 交换 字符swap(&str[m], &str[i]);//然后求一个后续的全排列perm(ans,str, m + 1, n);//然后交换回来swap(&str[m], &str[i]);}}return 0;
}
char** Permutation(char* str, int* returnSize ) {if(str==NULL){*returnSize=0;return NULL;}// write code herechar **ans=NULL;int len=strlen(str);ans=(char **)malloc(sizeof(char *)*1000);perm(ans,str,0,len);*returnSize=top;return ans;
}