문제 출처 : https://www.acmicpc.net/problem/15649

문제 파악

이 문제는 백트래킹 유형의 문제이다.

백트래킹이란
정답이 될 수 있는 모든 경우의 수를 만들어보다가,
가능하지 않은 길은 미리 되돌아오는 알고리즘 이다.

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 모두 출력하라.

N = 3, M = 2 라면

1 2
1 3
2 1
2 3
3 1
3 2

결과를 보면 다음을 알 수 있다.

숫자는 1부터 3까지 쓴다.
한 수열에는 같은 숫자가 없다.
첫 번째 자리에 1이 들어갔을 땐, 두 번째 자리엔 2,3이 올 수 있다.
첫 번째 자리에 2가 들어갔을 땐, 두 번째 자리엔 1,3이 올 수 있다.
즉, 모든 가능한 조합을 다 시도하되, 이미 쓴 숫자는 다시 안 쓴다.
이걸 코드로 옮긴 게 바로 백트래킹이다.

해답 코드

import sys
input = sys.stdin.readline

N, M = map(int,input().split()) 
nums = list(range(1, N+1)) # [1,2, ..., N]

path = [] # 현재까지 선택한 수열
used = [False] * N # 사용한 숫자 표시

def backtrack():
    if len(path) == M: # M개를 골라야하는데 path의 길이가 M개이다? 그러면 다 고른것이니 path를 print 해주고 백트래킹
        print(*path)
        return
    
    for i in range(N): # N번 만큼 반복할 것임
        if used[i]:
            continue # 다음 반복문 순회

        # 방문했던 used[i]가 아니라면
        used[i] = True
        path.append(nums[i])

        # 다음 깊이
        backtrack()

        # backtrack 해서 다시 이곳으로 돌아왔다면 마지막 요소 pop해주고 사용 안함 처리해주기
        path.pop()
        used[i] = False

# ---
backtrack()

nums 로 미리 N까지의 숫자를 list화 시켜놓은 것과,
path의 길이가 M이 되었을 떄 그때그때 *print를 해주고 return 하여 백트래킹 해준뒤
path.pop(), used[i]= False 처리로 되돌려 놓는 것을 기억하자.