組み合わせを求める


作成日:2022年2月6日午後8:44

インプリメンテーションコード

# 조합 구하기
import sys
sys.stdin = open("input.txt" ,"rt")

def DFS(L):
    global cnt
    if L == m:
        for x in res:
            print(x, end=' ')
        cnt += 1
        print()
    else:
        if L==0:
            for i in range(1, n+1):
                if ch[i] == 0:
                    ch[i] = 1
                    res[L] = i
                    DFS(L+1)
                    ch[i] = 0
        else:
            for i in range(res[L-1]+1, n+1):
                if ch[i] == 0:
                    ch[i] = 1
                    res[L] = i
                    DFS(L+1)
                    ch[i] = 0

if __name__ == "__main__":
    n, m = map(int, input().split())
    res = [0] * m
    ch = [0] * (n+1)
    cnt = 0
    DFS(0)
    print(cnt)

模範解答

import sys
sys.stdin=open("input.txt", "r")
def DFS(L, s):
    global cnt
    if L==m:
        for i in range(m):
            print(res[i], end=' ')
        print()
        cnt+=1
    else:
        for i in range(s, n+1):
            res[L]=i
            DFS(L+1, i+1)
           

n, m=map(int, input().split())
res=[0]*(n+1)
cnt=0
DFS(0, 1)
print(cnt)

差異

  • の基本論理は同じである.
  • で実装したコードでは、if L=0:条件文を使用して、resの0番目のインデックス(ツリーのレベル0)のすべての数字をnに加算し、res[L-1]+1からnの構造にします.
  • 母法解答では,sを再帰関数とするパラメータをL−1インデックスの値に加えた後,数からnの構造である.(コード簡略化)