acwing讲解篇之92. 递归实现指数型枚举

题目描述

题解思路

本题相当于二叉树的深度优先遍历，树的第i层是第i个数选或不选
我们记录当前递归的深度deep
然后用state进行状态压缩，state第i位是1表示选第i个数，第i位是0表示不选第i个数
进行dfs
如果当前深度为n，则说明当前已经递归完前n层，此时将state对应要选择的数打印出来，然后返回
深度加一
state不变动，表示不选当前层对应的数，然后进行递归
state当前位 置为1，表示选择当前层对应的数，然后进行递归
深度减一
state当前位 置为0

直到递归结束，程序退出

题解代码

n = int(input())
deep = 0
state = 0
def dfs():
    global deep
    global state
    if deep == n:
        for i in range(n):
            if state >> i & 1 == 1:
                print(i + 1, end=' ')
        print()
        return
    deep += 1
    dfs()
    state = state | 1 << (deep - 1)
    dfs()
    deep -= 1
    state -= 1 << deep
dfs()