题意：

输出字符串中字符的所有排列方式

要点：

回溯法可以将每种情况遍历一遍（注意跳过连续的相同的字符），重点在于排序，先排序再回溯可以保证输出按照字典序，但这题的排序不太一样：'A'<'a'<'B'<'b'<...<'Z'<'z'，所以cmp要分情况讨论才行

15178810

Accepted

164K

63MS

1004B

2016-02-19 21:22:48

#include
    
     #include
     
      #include
      
       char str[15], out[15];bool idx[15];int len;int cmp(const void *a, const void *b)//排序比较复杂，要分别考虑大小写{	char c = *(char *)a;	char d = *(char *)b;	if (c >= 97)	{		c -= 32;		if (d >= 97)		{			d -= 32;			return c - d;		}		else		{			if (c == d)				return 1;//A和a这种情况输出c
       
        = 97)		{			d -= 32;			if (c == d)				return -1;			else				return c - d;		}		return c - d;	}}void backtrace(int n){	if (n == len)	{		printf("%s\n", out);		return;	}	for (int i = 0; i < len; i++)	{		if (idx[i] == false)		{			out[n] = str[i];			idx[i] = true;			backtrace(n + 1); //标准回溯法			idx[i] = false;			int k = i + 1;  //跳过相同的			while (k < len&&str[k] == str[k - 1])				k++;			i = k - 1;  //i后面会i++，所以这里-1		}	}}int main(){	int t;	scanf("%d", &t);	while (t--)	{		memset(idx, false, sizeof(idx));		scanf("%s", str);		len = strlen(str);		out[len] = '\0';   //最后末尾加上字符串标识		qsort(str, len, sizeof(str[0]), cmp);		backtrace(0);	}	return 0;}