c++递归学习全组合排列



c++递归学习全组合排列

Sample Input

3

1 2 3

Sample Output

123

132

213

231

312

321

[cpp] view plaincopy


  1. #include <iostream>
  2. using namespace std;
  3. const int len = 10;
  4. int n;
  5. int mat[len];
  6. int result[len];
  7. bool used[len]; //初始值为false，表示都没有使用过
  8. void solve(int level);
  9. int main()
  10. {
  11.     cin>>n;
  12.     for (int i=0;i<n;i++)
  13.     {
  14.         cin>>mat[i];
  15.     }
  16.     solve(0);
  17.     system(“pause”);
  18.     return 0;
  19. }
  21. /*———————-
  22. 操作的目的：普通选择性组合排列
  23. 初始条件：
  24.     n:记录选取数据的总位数
  25.     mat数组:存储选取数据
  26.     used数组：标记是不是用过
  27.     result数组:存储已得到的结果
  28. 操作结果：
  29.     输出result数组，所有的选择性组合排列
  30. 函数参数:
  31.     level：既代表递归的层次，也代表result数组已经处理到第几位了
  32.     一句话就是：把没用过的数放到result数组的第level位上
  33. ————————*/
  34. void solve(int level)
  35. {
  36.     if (level == n)
  37.     {
  38.         for (int i=0;i<n;i++)
  39.         {
  40.             cout<<result[i];
  41.         }
  42.         cout<<endl;
  43.     }
  44.     else
  45.     {
  46.         for (int i=0;i<n;i++) //这里的for循环是从0开始的，与例子的输出是对应的
  47.         {
  48.             if (!used[i])//条件成立，没有用过
  49.             {
  50.                 result[level]=mat[i];
  51.                 used[i]=true;//标记已经用过
  52.                 solve(level+1);
  53.                 used[i]=false;
  54.             }
  55.         }
  56.     }
  57. }

注意：根据实例知，输出数据的时候，总是把所有数据都用过一边，无论该数字是在自己之前还是之后。

体现在具体的代码是在：

1、检测是不是被用过，这里引入used数组

2、递归入口的for循环中，for (int i=0;i<n;i++) 这里的for循环是从0开始的，也就是说每次往数组result中填数据的时候，都会查找一边数组mat，把每一个没用过的元素都用过一遍。