dfs

DFS基础

DFS和n重循环

模板

1
2
3
4
5
6
7
8
9
def dfs(depth):
    """
    :param depth: 记录当前深度
    :return 
    """
    if depth == N:
      # N重循环最内层执行的代码
        return # 结束条件
    # 每重循环进行的枚举选择

例题

1. 打印相加为X的非严格递增n位序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def dfs(depth, last_value):
    #depth:表示当前处于第depth层
    #递归入口
    if depth == n:
        #判断是否满足条件
        if sum(path) != x:
            return 
        
        print(path)
        return
    
    for i in range(last_value,x+1):
        path[depth] = i
        dfs(depth+1,i)

x = int(input())
n = int(input())

# path[i]表示第i个位置的值
path = [0]*n
# x = 6
# n = 3
# [0,0,0]


dfs(0,1)