DFS：深度优先搜索——本质上是暴力枚举，尽可能一条路走到底，走不了回退
1.DFS与n重循环
例：给定一个数字x，将其拆分为3个正整数，后一个要求大于前一个，给出方案。
分析：这种情况下就可以三重暴力循环破解
如果要拆分成n个正整数，就要实现n重循环
答题模板：不知道要进行多少次循环=n重循环=特定的树结构=DFS搜索
# 从用户处获取输入，x 表示生成序列中数字的和以及每个位置数字的取值上限（1 到 x）
# 最终生成的序列里所有数字相加要等于 x，且每个数字的取值范围是 1 到 x
x = int(input("请输入数字的和以及每个位置数字的取值上限 x: "))
# 从用户处获取输入n 表示要生成的序列深度
# 也就是最终生成的序列包含多少个数字
n = int(input("请输入要生成的序列的长度 n: "))
# 初始化用于存储当前生成序列的列表 path
# 先创建空列表，之后将其初始化为长度为 n 的列表，每个元素初始值为 0
# path 列表将在后续深度优先搜索过程中逐步填充数字，代表当前正在生成的序列
path = []
path = [0] * n
# 定义深度优先搜索函数 dfs，depth 表示当前正在处理序列的第几层
# last_value 表示上一层选择的数字，用于保证生成的序列是递增的
def dfs(depth, last_value):
# 递归出口条件：当 depth 等于 n 时，说明已经生成了一个完整的长度为 n 的序列
if depth == n:
# 检查序列中所有数字的和是否等于输入的 x
# 只有和为 x 的序列才是符合我们要求的序列
if sum(path) != x:
return
# 如果序列中数字的和等于 x，则打印该序列
print(path)
return
# 枚举当前位置（第 depth 个位置）可以取的值，范围是从 last_value 到 x
# 从 last_value 开始枚举能保证生成的序列是递增的，避免生成重复或递减的序列
for i in range(last_value, x + 1):
# 下一层从上一层的起点+1开始
# 比如说第一层选 3，第二层就要从 3 开始枚举，前面的 1 和 2 就不用考虑了，这样能保证是递增的
# 将当前枚举的值 i 赋给序列的第 depth 个位置
path[depth] = i
# 递归调用 dfs 函数，处理下一个位置（depth + 1）
# 同时将当前选择的数字 i 作为下一层的 last_value 传入，确保后续枚举是递增的
dfs(depth + 1, i+1)
# 启动深度优先搜索，从序列的第一个位置（depth = 0）开始
# 初始时上一层没有选择数字，所以 last_value 设为 0
dfs(0, 0)
#请输入数字的和以及每个位置数字的取值上限 x: 7
# 请输入要生成的序列的长度 n: 3
# [0, 1, 6]
# [0, 2, 5]
# [0, 3, 4]
# [1, 2, 4]提炼模板
def dfs(depth):
#当前为第几重循环
if depth==n: #如果是最后一重循环
return
#每重循环的枚举选择 
#分析：七个小朋友，所以是七重循环，n=7
# 每个小朋友得到的糖果2-5 2<=x<=5
ans=0
def dfs(depth,n,m):
if depth==7:
if n==0 and m==0:
global ans
ans=ans+1
return
#枚举当前小朋友的糖果可能性
#枚举第一种糖果
for i in range(0,6):
for j in range(0,6):
if 2<=i+j<=5 and i<=n and j<=m:
dfs(depth+1,n-i,m-j)
dfs(0, 9, 16)
print(ans)
# 5067671
# 分析：n重循环，每重循环三种情况：买一个，买半个，不买
def dfs(depth,weight,count):
if weight>m: #当前已经不合法，没必要继续下去
return
if weight==m:
global ans
ans=min(ans,count)
#depth:第depth个瓜
#weight:表示当前买到的瓜的重量
#count:表示劈了多少次
if depth==n:
return
#枚举瓜的三种情况
#不买
dfs(depth+1,weight+0,count)
#买
dfs(depth+1,weight+a[depth],count)
#买一半
dfs(depth+1,weight+a[depth]//2,count+1)
n,m=map(int,input().split()) #n表示n个瓜，m表示要买的重量
m=m*2 #为了比避免出现小数影响精度，所以都乘2
a=list(map(int,input().split())) #表示每个瓜的重量
a=[x*2 for x in a]
ans=n+1
dfs(0,0,0)
if ans==n+1:
ans=-1
print(ans)
