[算法][递归/栈]递归实现组合型枚举

递归实现组合型枚举

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

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

按照从小到大的顺序输出所有方案，每行 1 个。
首先，同一行内的数升序排列，相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）。
数据范围

n>0 ,
0≤m≤n  ,
n+(n−m)≤25
输入样例：

1. 5 3

复制代码

输出样例：

1. 1 2 3
2. 1 2 4
3. 1 2 5
4. 1 3 4
5. 1 3 5
6. 1 4 5
7. 2 3 4
8. 2 3 5
9. 2 4 5
10. 3 4 5

复制代码

思路一
递归
经过前两次的学习，已经基本掌握了递归的用法，但是在做这道题的时候还是出现了Time Limit Exceeded ，通过比较学习，记录一下自己欠缺的点

1. # --- 答案 ---
2. n, m = map(int, input().split())
3. num = []
5. def dfs(start, path):
6.     if len(path) == m:
7.         print(' '.join(map(str, path)))
8.         return
9.     # 剩余需选个数为 remain = m - len(path)
10.     # 当前数i的最大可能值为 n - remain + 1
11.     max_i = n - (m - len(path)) + 1
12.     for i in range(start, max_i + 1):
13.         dfs(i + 1, path + [i])
15. dfs(1, [])
17. # --- 自己写的 ---
18. n,m = map(int,input().split())
19. selected = [0]*(n+1)
20. num = [0]*(m+1)
21. def dfs(k, n, m):
22.     if k > m:
23.         for i in range(1,m+1):
24.             print(num[i], end=' ')
25.         print()
26.         return
27.     else:
28.         for i in range(1,n+1):
29.             if selected[i] == 0 and i> max(num):
30.                 selected[i] = 1
31.                 num[k] = i
32.                 dfs(k + 1, n, m)
34.                 selected[i] = 0
35.                 num[k] = 0
37. dfs(1,n,m)

复制代码

一些反思：

• 输出时 用join 链接，可以减少遍历
  
• 运用剪枝，缩小范围
  
• 减少数组，减少冗余
  

思路二
非递归[栈]

1. n, m = map(int, input().split())
3. if m == 0:
4.     print()
5.     exit()
7. stack = []
8. # 初始状态：可选的起始数字是1，当前路径为空
9. stack.append((1, []))
11. while stack:
12.     start, path = stack.pop()
13.    
14.     # 当路径长度足够时输出结果
15.     if len(path) == m:
16.         print(' '.join(map(str, path)))
17.         continue
18.    
19.     # 计算当前层可选数字的最大值（剪枝关键）
20.     remaining = m - len(path) - 1  # 后续还需要选remaining个数
21.     max_i = n - remaining
22.    
23.     # 倒序压栈，保证出栈顺序是正序（维持字典序）
24.     for i in range(max_i, start - 1, -1):
25.         new_path = path + [i]
26.         new_start = i + 1
27.         stack.append((new_start, new_path))

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！