[Brute Force]Boj 15652:NおよびM(4)

[Brute Force]Boj 15652:NおよびM(4)
link: https://www.acmicpc.net/problem/15652
質問する
自然数NとMが与えられた場合、以下の条件を満たすすべての長さMの数列を解くプログラムを作成します.

1からNまで、自然水中からM個の数列

を選ぶ.

などの数字を複数回選択できます.

の数列を選択するには、降雨順に並べます.

長さKの数列AはA 1≦A 2≦...≤AK-1≤AKが満たされた場合、降雨順と呼ぶ

入力

の第1行は、自然数NおよびMを与える.(1 ≤ M ≤ N ≤ 8)

しゅつりょく

行ごとに問題条件を満たす数列が出力されます.重複する数列は複数回出力できません.各数列はスペースで区切らなければなりません.

数列は、予めインクリメントされた順序で出力されるべきである.

I/O例

Code

import sys
si = sys.stdin.readline

N,M = list(map(int,si().split()))

def rec(K,N,M,selected):
    if K == M:
        for x in selected:
            print(x,end=" ")
        print()
    else:
        if K == 0: start = 1
        else: start = selected[K-1]
        for cand in range(start,N+1):
            selected[K] = cand
            rec(K+1,N,M,selected)

selected = [0 for _ in range(M)]
rec(0,N,M,selected)

Code Screenshot & Output