全排列（防止重复）

相信大家都知道什么是全排列，但是今天的全排列比你想象中的难一点。我们要找的是全排列中，排列结果互不相同的个数。比如：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 namespace std;
13 const int MAXN=1e3+5;
14 
15 char str[MAXN],buff[MAXN];
16 int vis[MAXN],cnt,len;
17 
18 void dfs(int num)
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             int j;
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 int main()
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 }