백준 15649번: N과 M python

문제 이해

이 문제는 자연수 N과 M이 주어졌을 때, 1부터 N까지의 수 중에서 중복 없이 M개를 고른 모든 순열을 출력하는 문제이다.
출력은 사전 순으로 정렬되어야 하며, 각 수는 한 번만 사용 가능하다.

1 ≤ M ≤ N ≤ 8

중복 없이, 순서를 고려한 조합 → 즉, 순열 문제이다.

내 해답

import sys
input = sys.stdin.readline

# N: 1부터 N까지의 숫자 중에서
# M: M개를 선택하여 순열을 만든다
N, M = map(int, input().split())

# 각 숫자의 방문 여부를 저장하는 리스트
visited = [False] * (N + 1)

# 현재까지 선택한 숫자들을 저장하는 리스트
result = []

# 백트래킹 함수 정의
def backtrack():
    # 만약 M개를 모두 선택했다면 출력하고 종료한다
    if len(result) == M:
        print(' '.join(map(str, result)))  # 공백으로 구분하여 출력
        return

    # 1부터 N까지 숫자 중에서
    for i in range(1, N + 1):
        if not visited[i]:  # 아직 사용하지 않은 숫자라면
            visited[i] = True      # 숫자를 사용했음을 표시하고
            result.append(i)       # 결과 리스트에 추가한다
            backtrack()            # 재귀 호출로 다음 숫자를 선택하러 간다
            result.pop()           # 재귀가 끝나고 돌아오면 마지막 숫자를 제거하고
            visited[i] = False     # 방문 표시도 다시 False로 되돌린다

# 백트래킹 함수 실행
backtrack()