백준 15649: N과 M (1)

재귀 함수에 백트래킹을 섞어서 풀어본 수열 출력 문제

import sys
input = sys.stdin.readline
n, m = map(int, input().split())

checked = [False] * (n + 1)
result = []

def recur(depth):
    # Stop
    if depth == m:
        print(*result)
        return
    
    # Main
    for i in range(1, n + 1):
        if not checked[i]:

            # Tracking
            checked[i] = True
            result.append(i)
            
            # Recursion
            recur(depth + 1)

            # Backtracking
            checked[i] = False
            result.pop()

recur(0)

트래킹 & 백트래킹 과정 상세 (n=m=3 가정)

• result = s, checked = v로 간단히 기록

'''
recur(0)
--> for i = 1, track: v = [T, F, F], s = [1]
    recur(0 + 1)
    --> for i = 1, skip
    --> for i = 2, track: v = [T, T, F], s = [1, 2]
        recur((0 + 1) + 1)
        --> print(*s): 1 2 and return
    --> for i = 2, backtrack: v = [T, F, F], s = [1]
    --> for i = 3, track: v = [T, F, T], s = [1, 3]
        recur((0 + 1) + 1)
        --> print(*s): 1 3 and return
    --> for i = 3, backtrack: v = [T, F, F], s = [1]
    --> return (automatically. for loop is done.)
--> for i = 1, backtrack: v = [F, F, F], s = []
--> for i = 2, track: v = [F, T, F], s = [2]
    recur(0 + 1)
    --> for i = 1, track: v = [T, T, F], s = [2, 1]
        recur((0 + 1) + 1)
        --> print(*s): 2 1 and return
    --> for i = 1, backtrack = [F, T, F], s = [2]
    --> for i = 2, skip
    --> for i = 3, track: v = [F, T, T], s = [2, 3]
        recur((0 + 1) + 1)
        --> print(*s): 2 3 and return
    --> for i = 3, backtrack: v = [F, T, F], s = [2]
    --> return (automatically. for loop is done.)
--> for i = 2, backtrack: v = [F, F, F], s = []
--> for i = 3, track: v = [F, F, T], s = [3]
    recur(0 + 1)
    --> for i = 1, track: v = [T, F, T], s = [3, 1]
        recur((0 + 1) + 1)
        --> print(*s): 3 1 and return
    --> for i = 1, backtrack: v = [F, F, T], s = [3]
    --> for i = 2, track: v = [F, T, T], s = [3, 2]
        recur((0 + 1) + 1)
        --> print(*s): 3 2 and return
    --> for i = 2, backtrack: v = [F, F, T], s = [3]
    --> for i = 3, skip
    --> return (automatically. for loop is done.)
--> for i = 3, backtrack: v = [F, F, F], s = []
--> return (automatically. for loop is done.)
'''