[BOJ]15650-NとM(2)

展開

に近づく

1からNまでの数字の中から、M個の数列を選択して昇順で出力します.
まず、復帰で解決できると思います.そして、久しぶりにDFSを実装してから、やっと意識不明の時に実行するコードを書くことができました(…).

コード#コード#

from sys import stdin

N, M = tuple(int(i) for i in stdin.readline().split())

def search(answer, depth, next_idx):
    global N, M

    if depth == M:
        print(" ".join(answer))
        return

    for i in range(next_idx, N + 1):
        answer += str(i)
        search(answer, depth + 1, i + 1)
        answer.pop()

search([], 0, 1)

一般的なDFSで使用されるアクセスの有無配列は、この問題では書く必要はありません.元のデータはアルファベット順に並べ替えられているため,次のナビゲーション範囲を調整するだけで繰返しナビゲーションを防止できるといえる.
backtracking問題がまだ解決されていないためかDFSと何が違うのか疑問に思っていたので少し理解しました.実施から見ると事実上は同じだが,解題策を策定する際には観点が異なるようだ.オーストラリアみたいな感じかな?