C语言实现字符串的全排列

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到ans
	if (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 here
    char **ans=NULL;
    int len=strlen(str);
    ans=(char **)malloc(sizeof(char *)*1000);
    perm(ans,str,0,len);
    *returnSize=top;
    return ans;
}