c++非重复生成全子集组合排列（含重复数字时，生成不重复全子集组合排列）



c++非重复生成全子集组合排列（含重复数字时，生成不重复全子集组合排列）。

Sample Input

4

1 2 2 3

Sample Output

1

12

122

1223

123

13

2

22

223

23

3

如果采用上篇文章的程序(处理不含重复数)，运行的结果是：


以上均为重复数据，上标表示在原数据中使用的是重复数据的第几个数据，这就多出来好几种。

出现这种情况的原因是：在mat中存有重复的数据，在赋值的时候，仍然把这些数据取出直接赋值到数组result中。

要避免这种情况，就引入两个数组mat和 used数组：

mat数组：一个存放不重复数据的数据

used数组：存放每个数据出现的次数

在递归过程中，使用mat为数组result直接赋值。在赋值时，由于使用不重复数据的数据mat数组直接对其进行赋值，这就避免出现121 和122情况了。

但是，使用这种存储的方式，就会把应该出现的数据也给扼杀了，如1223。这里的做法是 递归传值的时候，mat数组中每一位数据可以重复传一次，检测是不是重复出现过。

具体表现是solve(cur_totalVar+1,i)中的i，即下一次取数的下标是i，而i是本次递归刚刚处理过下标i的位置，使用这样的方法，就可以连续的检测某一个数是不是重复出现了，

进而可以连续的读取。

  1. #include <iostream>
  2. using namespace std;
  3. const int len=10;
  4. int n;
  5. int num;//不重复的实际个数
  6. int mat[len];
  7. int result[len];
  8. int used[len];
  9. void push(int varNum);
  10. void solve(int cur_totalVar,int nextVar);
  11. int main()
  12. {
  13.     cin>>n;
  14.     num=0;
  15.     int var;
  16.     for (int i=0;i<n;i++)
  17.     {
  18.         cin>>var;
  19.         push(var);
  20.     }
  21.     solve(0,0);
  22.     system(“pause”);
  23.     return 1;
  24. }
  25. /*———————-
  26. 操作的目的：生成一个数据全不重复的数组,并记录每个数出现的次数
  27. 操作结果：
  28.     num记录不重复数的个数(mat数组中数据的长度)
  29.     mat数组存储不重复的数据
  30.     used数组统计对应mat数组位置数据的出现次数
  31. 函数参数：
  32.     varNum：存储刚刚输入的数据，用来检测是不是重复的数据
  33. ————————*/
  34. void push(int varNum)
  35. {
  36.     for (int i=0;i<num;i++)
  37.     {
  38.         if (mat[i]==varNum)
  39.         {
  40.             used[i]++;
  41.             return;
  42.         }
  43.     }
  44.     mat[num]=varNum;
  45.     used[num]++;
  46.     num++;
  47. }
  49. /*———————-
  50. 操作的目的：生成全子集组合排列（含重复数据）
  51. 初始条件：
  52.     num记录不重复数的个数(mat数组中数据的长度)
  53.     mat数组存储不重复的数据
  54.     used数组统计对应mat数组位置数据的出现次数
  55. 操作结果：
  56.     输出全部子集
  57. 函数参数：
  58.     cur_totalVar：针对输出数组result，表示现在要存放数据的位置，之后也控制着输出
  59.     nextVar：针对原存储数组mat，表示下一个要读取数据的位置
  60. ————————*/
  61. void solve(int cur_totalVar,int nextVar)
  62. {
  63.     for (int i=0;i<cur_totalVar;i++)
  64.     {
  65.         cout<<result[i];
  66.     }
  67.     cout<<endl;
  68.     for (int i=nextVar;i<num;i++)
  69.     {
  70.         if (used[i])
  71.         {
  72.             result[cur_totalVar]=mat[i];
  73.             used[i]–;
  74.             solve(cur_totalVar+1,i);
  75.             /*这里的参数i表示：数组mat中下一个要处理的数是本次函数刚刚处理过的，
  76.                 这里还要在检查一遍，就是为了处理有数据重复的情况,如果数据不重复，就使用i+1*/
  77.             used[i]++;//恢复现场
  78.         }
  79.     }
  80. }
  82. /*
  83. 算法的思想：
  84. 函数思想：使用for循环遍历原存储数据的数组mat，边遍历边对输出数组result赋值，同时进行递归.
  85. 为了处理重复的数据，就让mat数组存储不重复的数据，在为数组result赋值时，使用这个不重复的数组进行赋值，
  86. 但是要处理重复的数据的话，在递归传递参数的时候，把刚刚处理过的数据再传进去一遍，在进行一下处理，检测是不是有重复，若重复，就可以再使用一次。但是这里的重复使用时不会出现重复的数据的，具体可以写一下递归的过程分析一下。其中还是数组mat起了关键作用。
  87. 忽略递归，从for循环来看，存储数组中要存放数据的位置cur_totalVar是固定的，使用for循环对result进行赋值，
  88. 这样就可以让输出数组中同一个位置有多个变化的变量。这时，在看递归，当结果数组的cur_totalVar位置已经赋值成功后，
  89. 之后应该是对结果数组result的cur_totalVar+1的位置使用原数组mat的i+1位置的数据进行赋值(第i个数据已经赋过值了)–这里先不考虑重复数据。
  90. 如果考虑重复的位数，当然应该是传入mat中第i位，看是不是重复。*/