acwing讲解篇之93. 递归实现组合型枚举

发布时间:2024年01月20日

题目描述

在这里插入图片描述

题解思路

本题相当于二叉树的深度优先遍历,树的第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 deep
    global state
    global count
    if n - deep < m - count:
        return
    if count == m:
        for i in range(n):
            if state >> i & 1 == 1:
                print(i + 1, end = ' ')
        print()
        return

    state |= 1 << deep
    deep += 1
    count += 1
    dfs()
    state -= 1 << (deep - 1)
    count -= 1
    
    dfs()
    deep -= 1
dfs()
文章来源:https://blog.csdn.net/qq_67733273/article/details/135718299
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。