摘要：
相信大家都知道什么是全排列，但是今天的全排列比你想象中的难一点。我们要找的是全排列中，排列结果互不相同的个数。但是有一个问题就是如何去防止重复呢？先想一下简化的问题吧，假如输入的字符串不重复，例如abcd，那么就是简单的dfs了，一个for循环加一个vis判断，如果判断可以，继续递归。当有重复的字符时候就比较麻烦了，比如aab，单纯的用递归会输出重复的。
相信大家都知道什么是全排列，但是今天的全排列比你想象中的难一点。我们要找的是全排列中，排列结果互不相同的个数。比如：aab的全排列就只有三种，那就是aab,baa,aba。
思路：
这道题的思路其实挺简单的，就是dfs去搜索就可以了。
但是有一个问题就是 如何去防止重复呢？
先想一下简化的问题吧，假如输入的字符串不重复，例如abcd，那么就是简单的dfs了，一个for循环加一个vis判断，如果判断可以，继续递归。
当有重复的字符时候就比较麻烦了，比如aab，单纯的用递归会输出重复的。那么怎么加上限定条件呢。
这里，我们让重复的这些字符只顺序输出一遍，这样就不会重复
这是什么意思呢，比如说aabc,我们只允许第一个a访问后再访问第二个a，不允许访问第二个，再第一个。
再如，abacda，那三个a只能按顺序访问。
原理是什么呢，用了点高中学的排列组合的知识，先排重复的，例如我们搞abacda这个例子, 先排三个a, 就是 aaa,那么剩下的就相当于直接插入到aaa中，那么如果我们aaa如果按多种顺序排，就会产生多种结果，所以只能按顺序访问。
那么又如何用算法实现呢，直接加个if判断就行了，判断i之后的有没有访问过的且相等的。例如，aabc这个例子，我们第一轮选完之后，到了第二个a,然后进入递归，for循环又从0开始，到了第一个a，然后从这个之后去判断有没有访问过的a，结果判断有，违反了顺序，所以结束。
这个题目的关键也就是排除重复的
1 #include <iostream> 2 #include <algorithm> 3 #include <stdlib.h> 4 #include <string> 5 #include <string.h> 6 #include <set> 7 #include <queue> 8 #include <stdbool.h> 9 10 #define LL long long 11 #define inf 0x3f3f3f3f 12 using namespacestd; 13 const int MAXN=1e3+5; 14 15 charstr[MAXN],buff[MAXN]; 16 intvis[MAXN],cnt,len; 17 18 void dfs(intnum) 19 { 20 if (num ==len) 21 { 22 cnt++; 23 printf("%s ",buff); 24 return; 25 } 26 for (int i=0;i<len;i++) 27 { 28 if (!vis[i]) 29 { 30 intj; 31 for (j=i+1;j<len;j++) 32 { 33 if (str[i]==str[j] &&vis[j]) 34 { 35 break; 36 } 37 } 38 if (j ==len) 39 { 40 vis[i] = 1; 41 buff[num] =str[i]; 42 dfs(num+1); 43 vis[i] = 0; 44 } 45 } 46 } 47 48 } 49 50 51 52 intmain() 53 { 54 #ifndef ONLINE_JUDGE 55 freopen("../in.txt","r",stdin); 56 #endif 57 while (~scanf("%s",str)) 58 { 59 len =strlen(str); 60 sort(str,str+len); 61 cnt = 0; 62 memset(vis,0, sizeof(vis)); 63 dfs(0); 64 printf("%d ",cnt); 65 } 66 return 0; 67 }