[算法][递归/栈]递归实现组合型枚举
递归实现组合型枚举从 1∼n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。
输入格式
两个整数 n,m ,在同一行用空格隔开。
输出格式
按照从小到大的顺序输出所有方案，每行 1 个。
首先，同一行内的数升序排列，相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）。
数据范围
n>0 ,
0≤m≤n,
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 思路一
递归
经过前两次的学习，已经基本掌握了递归的用法，但是在做这道题的时候还是出现了Time Limit Exceeded ，通过比较学习，记录一下自己欠缺的点
# --- 答案 ---
n, m = map(int, input().split())
num = []
def dfs(start, path):
if len(path) == m:
print(' '.join(map(str, path)))
return
# 剩余需选个数为 remain = m - len(path)
# 当前数i的最大可能值为 n - remain + 1
max_i = n - (m - len(path)) + 1
for i in range(start, max_i + 1):
dfs(i + 1, path + )
dfs(1, [])
# --- 自己写的 ---
n,m = map(int,input().split())
selected = *(n+1)
num = *(m+1)
def dfs(k, n, m):
if k > m:
for i in range(1,m+1):
print(num, end=' ')
print()
return
else:
for i in range(1,n+1):
if selected == 0 and i> max(num):
selected = 1
num = i
dfs(k + 1, n, m)
selected = 0
num = 0
dfs(1,n,m)一些反思：
[*]输出时 用join 链接，可以减少遍历
[*]运用剪枝，缩小范围
[*]减少数组，减少冗余
思路二
非递归[栈]
n, m = map(int, input().split())
if m == 0:
print()
exit()
stack = []
# 初始状态：可选的起始数字是1，当前路径为空
stack.append((1, []))
while stack:
start, path = stack.pop()
# 当路径长度足够时输出结果
if len(path) == m:
print(' '.join(map(str, path)))
continue
# 计算当前层可选数字的最大值（剪枝关键）
remaining = m - len(path) - 1# 后续还需要选remaining个数
max_i = n - remaining
# 倒序压栈，保证出栈顺序是正序（维持字典序）
for i in range(max_i, start - 1, -1):
new_path = path +
new_start = i + 1
stack.append((new_start, new_path))
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]