题目描述

题解思路

本题相当于二叉树的深度优先遍历，树的第i层表示第i个数选或不选，当选择了m次左节点后退出
我们记录当前递归的深度deep
然后用state进行状态压缩，state第i位是1表示选第i个数，第i位是0表示不选第i个数
count表示我们选择数的个数

进行dfs

当前还能选择的数的个数即n - deep，当前还应选择的数的个数即m - count
如果当前还能选择的数的个数小于当前还应选择的数的个数，则退出搜索

如果当前选择的数的个数为m，则说明当前数已经选完，此时将state对应要选择的数打印出来，然后返回

state当前位 置为1，深度加一，当前选择的数的个数加一，表示选择当前层对应的数，然后进行递归

恢复state和count当前层初始的state和count
进行递归
深度减一

直到递归结束，程序退出

题解代码

n, m = map(int, input().split())deep = 0
state = 0
count = 0
def dfs():global deepglobal stateglobal countif n - deep < m - count:returnif count == m:for i in range(n):if state >> i & 1 == 1:print(i + 1, end = ' ')print()returnstate |= 1 << deepdeep += 1count += 1dfs()state -= 1 << (deep - 1)count -= 1dfs()deep -= 1
dfs()