AcWing递归实现组合型枚举

• 题目

题目

从 1∼n这 n个整数中随机选出 m个，输出所有可能的选择方案。

输入格式

两个整数 n,m ,在同一行用空格隔开。

输出格式

按照从小到大的顺序输出所有方案，每行 1 个。

首先，同一行内的数升序排列，相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）。

数据范围

n>0n>0 , 0≤m≤n； n+(n−m)≤25

题解

非递归

首先考虑非递归的思路，一共有2^n的情况，使用位运算，每一位代表该数字是否出现，0代表不包含，1代表包含。题目要求按顺序输出，那么我们将答案存储，然后排序即可。

由题目可知0<n<=25;所以时间复杂度上可行。

接着考虑空间复杂度；将限制条件（0≤m≤n；n+(n−m)≤25）画出得到所有取值范围。然后根据排列组合可以知道当n为m的2倍的时候所有可能的组合的数量最大,画y=2x的图像与其交点，得到此题目当x=8.3的时候最大，那么答案最多就是C（8，17）。计算得到大概空间在2e4左右，所以空间上也符合。

 

 

 #include <bits/stdc++.h>
 #define INF 0x3f3f3f3f
 using namespace std;
 typedef long long LL;
 const int N = 3e4 + 5;
 int n, m;
 vector<int> s[N];
 int main()
 {
     scanf("%d %d", &n, &m);
     int all = 1 << n;
     int sum = 0;
     for (int i = 1; i < all; i++)
     {
         int x = i, t = 0, num = 0;
         while (x)
         {
             t++;
             if (x & 1) num++;
             x >>= 1;
         }
         if (num == m)
         {
             x = i; t = 0;
             while (x)
             {
                 t++;
                 if (x & 1) s[sum].push_back(t);
                 x >>= 1;
             }
             sum++;
         }
     }
     sort(s, s + sum);
     for (int i = 0; i < sum; i++)
     {
         for (auto j : s[i])
         {
             printf("%d ", j);
         }
         printf("\n");
     }
 }

递归

对每一个数选或者不选即可，由于题目按照从小到达输出，所以我们每次从小到大选择，优先考虑选择此数字，再考虑不选此数字。

 #include <bits/stdc++.h>
 #define INF 0x3f3f3f3f
 using namespace std;
 typedef long long LL;
 const int N = 3e4 + 5;
 int n, m;
 vector<int> vt;
 void dfs(int t)
 {
     if (vt.size() == m)
     {
         for (auto i : vt)
         {
             printf("%d ", i);
         }
         printf("\n");
         return;
     }
     if (t > n)return;
     vt.push_back(t);
     dfs(t + 1);
     vt.pop_back();
     dfs(t + 1);
 }
 int main()
 {
     scanf("%d %d", &n, &m);
     dfs(1);
 }