摘要
Title: 93. 递归实现组合型枚举
Tag: 组合、排列、二进制枚举
Memory Limit: 64 MB
Time Limit: 1000 ms

93. 递归实现组合型枚举

题意

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

递归版：
- 首先path数组表示路径，st数组表示这个数用没用过
- 其次 $dfs$ 有一个参数，代表path数组的下标， $path[u] = i$ 代表这个排列的第u个数是i
- 排列和组合在递归时的唯一区别：数是否有序
  - 也就是说，当排列规定一个顺序之后，就会从排列变为组合
  - 所以就在排列的代码上，加上一句规定升序的顺序即可
非递归版：
- 最普通的二进制枚举，会多一个排序的复杂度，会更慢一些

代码

递归版

'''
Author: NEFU AB-IN
Date: 2022-03-21 21:11:14
FilePath: \ACM\Acwing\93.1.py
LastEditTime: 2022-03-21 21:11:14
'''
N = 50
st, path = [0] * N, [0] * N


def dfs(u):
    if u > m:
        for i in range(1, m + 1):
            print(path[i], end=" ")
        print()
        return
    for i in range(1, n + 1):
        if st[i] == 0 and (u == 1 or i > path[u - 1]):
            st[i] = 1
            path[u] = i
            dfs(u + 1)
            st[i] = 0


n, m = map(int, input().split())
dfs(1)

非递归版

'''
Author: NEFU AB-IN
Date: 2022-03-21 20:58:30
FilePath: \ACM\Acwing\93.py
LastEditTime: 2022-03-21 20:58:30
'''
n, m = map(int, input().split())

res = []
for i in range(1 << n):
    ans = []
    for j in range(n):
        if i & 1 << j:
            ans.append(j + 1)
    if len(ans) == m:
        res.append(ans)

res.sort()

for num in res:
    for i in num:
        print(i, end=" ")
    print()

93. 递归实现组合型枚举

题意

思路

代码