BOJ DFS(逆追跡):NとM(1)(15649)

質問する
自然数NとMが与えられた場合、以下の条件を満たすすべての長さMの数列を解くプログラムを作成します.
1からNまで自然数の中でM個の数列を繰り返し選択しない
入力
第1行は自然数NとMを与える.(1 ≤ M ≤ N ≤ 8)
しゅつりょく
各行に問題条件を満たす数列を出力します.重複する数列は複数回出力できません.各数列はスペースで区切らなければなりません.
数列は予め増加した順序で出力しなければならない.
I/O例

試す

の正解がありますが、ランタイムエラー

が発生しました.

# itertools의 combination은 순서에 따라 중복X
# itertools의 permutations은 순서 상관없이 중복O

from itertools import permutations as p

n, m = map(int, input().split(' '))
n, m = 4, 2
lst = [x for x in range(1, n+1)]
for i in  p(lst,m):
    print(i[0], i[1])

解答コード1:itertoolsを利用

from itertools import permutations as p

n, m = map(int, input().split(' '))
n, m = 4, 2

lst = [x for x in range(1, n+1)]
lst_p = list(p(lst, m))

for i in range(len(lst_p)):
    for j in range(m):
        print(lst_p[i][j], end = " ")
    print()

正しいコード2:遡及を利用する

n, m = 3, 2
def dfs():
    if len(lst) == m:
        print(' '.join(map(str,lst)))
        return
    for i in range(1, n+1):
        if i not in lst:
            lst.append(i)
            dfs()
            lst.pop()
dfs()

遡及はDFSベースの応用アルゴリズムである.
与えられた問題の答えを解くために,現在の状態で可能な限りすべての候補群に従って探索するアルゴリズム.
BOJのNとM(1-9)シリーズはバックグラウンドの練習にぴったりです.

バックグラウンドトラッキングに基づいて,再帰関数を再理解するためにコード実行順序を整理した.

FIRST MAIN LOOP #############################################################

dfs1 : i == 1 : [1]     # append

dfs2 : i == 1 : ----------------

dfs2 : i == 2 : [1,2]   # append
dfs3 : return [1,2]
dfs2 : i == 2 : [1]     # pop

dfs2 : i == 3 : [1,3]   # append
dfs4 : return [1,3]
dfs2 : i == 3 : [1]     # pop

dfs1 : i == 1 : []      # pop

SECOND MAIN LOOP #############################################################

dfs1 : i == 2 : [2]     # append

dfs5 : i == 1 : [2,1]   # append
dfs6 : return [2,1]
dfs5 : i == 1 : [2]     # pop

dfs5 : i == 2 : ----------------

dfs5 : i == 3 : [2,3]   # append
dfs7 : return [2,3]
dfs5 : i == 3 : [2]     # pop

dfs1 : i == 2 : []      # pop

THIRD MAIN LOOP #############################################################

dfs1 : i == 3 : [3]     # append

dfs8 : i == 1 : [3,1]   # append
dfs9 : return [3,1]
dfs8 : i == 1 : [3]     # pop

dfs8 : i == 2 : [3,2]   # append
dfs10: return [3,2]
dfs8 : i == 2 : [3]     # pop

dfs8 : i == 3 : -----------------

dfs1 : i == 3 : []      # pop

#############################################################