洛谷P1157 组合的输出（Python）

伤痕，是男子汉的勋章。

——圣斗士星矢

一、题目

P1157 组合的输出https://www.luogu.com.cn/problem/P1157

二、代码

def pri(L):
    for i in range(len(L)):
        if L[i]==True:
            print("{:3d}".format(i),end='')

def dfs(n,r,cur,count):  #n,r为题意，cur为当前考虑的数，count为已经加入排列中的数
    global L
    if count==r:  #这里cur>n
        pri(L)
        print()
    else:
        if cur<=n:  #防止数组越界
            L[cur]=True
            dfs(n,r,cur+1,count+1)
            L[cur]=False
            dfs(n,r,cur+1,count)


n,r = map(int,input().strip().split())
L = [False]*(n+1)
dfs(n,r,1,0)

三、总结

①dfs函数的写法可以作为排列组合的模版；

②递归时，这一层的count是对上一层决策的判断，count和cur不是对应的，所以一定要做数组越界判断。