递归dfs入门
做题方法：确定枚举顺序，画出递归树
递归实现指数型枚举
题目编号：
acwing.92.递归实现指数型枚举
题目描述：
从 1∼n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。
输入格式：
输入一个整数 n。
输出格式：
每行输出一种方案。
同一行内的数必须升序排列，相邻两个数用恰好 1 个空格隔开。
对于没有选任何数的方案，输出空行。
本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。
数据范围：
1 ≤ n ≤ 15
输入样例：
3
输出样例：
3
2
2 3
1
1 3
1 2
1 2 3
递归树：
代码实现：
def dfs(i):global state,n#首先确定递归边界if i>n:for j in range(1,n+1):if state[j]==1:print(j,end=' ')print('')return#分支1：选state[i]=1dfs(i+1)#恢复状态state[i]=0#分支2：不选state[i]=2dfs(i+1)state[i]=0
n=int(input())
#共有三个状态:0表示待考虑 1表示选 2表示不选
state=[0 for i in range(n+1)]
#从第一个位置开始枚举
dfs(1)
原题链接：link
递归实现排列型枚举
题目编号：
acwing.94.递归实现排列型枚举
题目描述：
把 1∼n这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。
输入格式：
一个整数 n。
输出格式：
按照从小到大的顺序输出所有方案，每行 1 个。
首先，同一行相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。
数据范围：
1 ≤ n ≤ 9
输入样例：
3
输出样例：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
递归树：
代码实现：
def dfs(i):global n,path,usedif i>n:for x in range(1,n+1):print(path[x],end=' ')print('')return#枚举每个分支，从小到大#即当前位置可以填哪个数for j in range(1,n+1):if used[j]==False:path[i]=jused[j]=Truedfs(i+1)path[i]=0used[j]=False
n=int(input())
#依次枚举每个位置都存哪个数
#path表示每个位置存的什么数
path=[0 for i in range(n+1)]
#used存每个数是否用过
used=[False for i in range(n+1)]
dfs(1)
原题链接：link
递归实现组合型枚举
题目编号：
acwing.93.递归实现组合型枚举
题目描述：
从 1∼n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。
输入格式：
两个整数 n,m ,在同一行用空格隔开。
输出格式：
按照从小到大的顺序输出所有方案，每行 1 个。
首先，同一行内的数升序排列，相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）。
数据范围：
n > 0,
0 ≤ m ≤ n ,
n+(n−m) ≤ 25
输入样例：
5 3
输出样例：
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
递归树：
与递归实现排列型枚举的递归树一样，只不过可选数字的范围变成1~n，每次选择的数字必须大于前边的数字，并且位数限制在m位。
代码实现：
升序考虑：
def dfs(i):global used,state,n,m,tmpif i>m:for i in range(1,m+1):print(state[i],end=' ')print('')return#保持升序选择#局部考虑 加限制条件#只需要保证新加的数大于前边的数即可for j in range(tmp,n+1):if used[j]==False:state[i]=jused[j]=Truetmp=jdfs(i+1)state[i]=0used[j]=False
n,m=map(int,input().split())
#每个数的状态 是否使用过
used=[False for i in range(n+1)]
#每个位置的状态 即每个位置填什么数
state=[0 for i in range(m+1)]
tmp=1
dfs(1)
降序考虑：
def dfs(i):global used,state,n,m,tmpif i>m:for i in range(1,m+1):print(state[i],end=' ')print('')return#保持降序选择#局部考虑#只需要保证新加的数小于前边的数即可for j in range(1,tmp+1):if used[j]==False:state[i]=jused[j]=Truetmp=jdfs(i+1)state[i]=0used[j]=False
n,m=map(int,input().split())
#每个数的状态 是否使用过
used=[False for i in range(n+1)]
#每个位置的状态 即每个位置填什么数
state=[0 for i in range(m+1)]
tmp=n
dfs(1)
原题链接：link