递归实现三类枚举

lyz103 / 2023-04-28 / 原文

1.递归实现组合类枚举
组合类枚举：从n中选s个数的所有组合

n = 0
m = 0

def dfs(u : int, s : int, state : int):
    if s == m:
        for i in range(0 , n):
            if state >> i & 1:
                print(i + 1, end=' ')
        
        print("")
        return 
    
    if u == n :
        return 
    for i in range (u , n):
        dfs(i + 1, s + 1, state + (1 << i))

n,m = map(int ,input().split())

dfs(0 ,0 ,0)

2.递归实现排列型枚举
排列型枚举就是获取n个数的全排列

n = 0
path = []

def dfs(u : int, state : int) :
    if u == n:
        for x in path :
            print(x,end=' ')
        print()
        return
    
    for i in range(0 , n):
        if not (state >> i & 1):
            path.append(i + 1)
            dfs(u + 1, state + (1 << i))
            del(path[-1])

n = int(input())
dfs(0 , 0)

3.递归实现指数类枚举
指数类枚举： 1∼n 这 n 个整数中随机选取任意多个

n = 0

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

dfs(0,0)