AcWing 93.递归实现组合型枚举
从 1 ∼ n 1∼n 1∼n 这 n n n 个整数中随机选出 m m m 个,输出所有可能的选择方案。
两个整数 n , m n,m n,m,在同一行用空格隔开。
按照从小到大的顺序输出所有方案,每行 1 1 1 个。
首先,同一行内的数升序排列,相邻两个数用一个空格隔开。
其次,对于两个不同的行,对应下标的数一一比较,字典序较小的排在前面(例如 1 3 5 7 排在 1 3 6 8 前面)。
n
>
0
n>0
n>0,
0
≤
m
≤
n
0≤m≤n
0≤m≤n,
n
+
(
n
−
m
)
≤
25
n+(n−m)≤25
n+(n−m)≤25
5 3
1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5
思考题:如果要求使用非递归方法,该怎么做呢?
采用递归做法时,只需在递归实现指数型枚举的递归函数中加上剪枝:
代码 (递归):
#include <iostream> #include <vector> using namespace std; int n, m; vector <int> num; void work(int x){<!-- --> if (num.size() > m || num.size() + n - x + 1 < m) return; if (x == n + 1){<!-- --> for (int i = 0; i < num.size(); i ++) cout << num[i] << " "; cout << endl; } num.push_back(x); work(x + 1); num.pop_back(); work(x + 1); } int main(){<!-- --> cin >> n >> m; if (m == 0) return 0; //特判 work(1); }
当然,也可以通过枚举二进制数,计算其中 1 1 1 的个数来判断合法性来做。此做法中遇到的最大困难是按照字典序输出。为此,我们可以定义结构体存储二进制数,并自定义比较函数来按照字典序排序。
代码 (非递归):
#include <iostream> #include <algorithm> using namespace std; int n, m, cnt; int num[30]; struct binary{<!-- --> //定义结构体,方便按照字典序排序 int k; }a[1 << 15]; bool cmp(binary a, binary b){<!-- --> //定义按照字典序排序的比较函数 for (int i = 0; i < n; i ++){<!-- --> int _a = a.k >> i & 1, _b = b.k >> i & 1; if (_a != _b) return _a > _b; } } int popcount(int x){<!-- --> //统计二进制数中1的个数 int n = 0; while (x){<!-- --> n += x & 1; x >>= 1; } return n; } int main(){<!-- --> cin >> n >> m; for (int i = 0; i < n; i ++) num[i] = i + 1; for (int i = 0; i < 1 << n; i ++) if (popcount(i) == m) a[cnt ++].k = i; sort(a, a + cnt, cmp); for (int i = 0; i < cnt; i ++){<!-- --> for (int j = 0; j < n; j ++) if (a[i].k >> j & 1) cout << num[j] << " "; cout << endl; } }