给出一个有重复元素的数组， 生成他的全排列
解释一下刘汝佳的代码 ： 就是这个递归只会考虑相同元素的第一个， 所以与前一个相同的元素应当被忽略， 第一个元素由于没有前面的元素， 所以应当取走。
注意这一行代码：
观察用例 3 1 1 1
有了这行代码 只会输出一个 1 1 1
但没有这行代码 就会输出27 个 1 1 1 （3层循环， 每层3个 3^3）
...
1 // 可重集的全排列 2 // Rujia Liu 3 #include<cstdio> 4 #include<algorithm> 5 using namespace std; 6 7 int P[100], A[100]; 8 9 // 输出数组P中元素的全排列。数组P中可能有重复元素 10 void print_permutation(int n, int* P, int* A, int cur) { 11 if(cur == n) { 12 for(int i = 0; i < n; i++) printf("%d ", A[i]); 13 printf(" "); 14 } else 15 for(int i = 0; i < n; i++) 16 //p[i] == p[i-1]的话，那么p[i]这个数只考虑p[i-1]的就行 17 //i == 0 时 那么必定要取 因为没有比它更前的可以考虑 18 if(!i || P[i] != P[i-1]) { 19 int c1 = 0, c2 = 0; 20 //A是已经填进去的， P是还没有填的 21 //用c1 c2统计已经填进去的个数和全部， 如果c1 < c2说明有没填进去的 22 for(int j = 0; j < cur; j++) 23 if(A[j] == P[i]) c1++; 24 25 for(int j = 0; j < n; j++) 26 if(P[i] == P[j]) c2++; 27 printf("!%d ", i);//标记一下选的下标 28 if(c1 < c2) { 29 printf("$%d ^%d ", i, cur);// 30 A[cur] = P[i]; 31 print_permutation(n, P, A, cur+1); 32 } 33 } 34 } 35 36 int main() { 37 int i, n; 38 scanf("%d", &n); 39 for(i = 0; i < n; i++) 40 scanf("%d", &P[i]); 41 sort(P, P+n); 42 print_permutation(n, P, A, 0); 43 return 0; 44 }