📌 문제 요약

• 문제 이름: 15649번: N과 M (1)
• 알고리즘 분류: 백트래킹 (Backtracking)
• 사용 언어: Python 3

자연수 $N$과 $M$이 주어졌을 때, 1부터 $N$까지 자연수 중에서 중복 없이 $M$개를 고른 수열을 모두 구하는 문제입니다. 오름차순 조건이 없으므로 (1, 2)와 (2, 1)은 서로 다른 수열로 취급되는 전형적인 순열(Permutation) 문제입니다.

---

💡 문제 접근 방법 (핵심 로직)

N과 M (2) 문제가 '조합'이었다면, 이 문제는 '순열'입니다. 따라서 다음 탐색을 진행할 때 이전에 고른 숫자보다 큰 수만 고를 필요가 없습니다. 항상 1부터 N까지 다시 탐색하되, "이미 수열에 포함된 숫자만 제외"하면 됩니다.

1. 항상 1부터 N까지 순회: for i in range(1, N + 1)을 사용하여 매 재귀마다 모든 숫자를 검사합니다.
2. 중복 방지 (방문 처리): if i not in result: 조건을 추가합니다. 만약 result 배열에 이미 i가 들어있다면, 중복을 허용하지 않으므로 건너뜁니다.
3. 백트래킹 (상태 복구): 조건을 통과한 숫자는 result.append(i)로 넣고 재귀를 호출한 뒤, 탐색이 끝나고 돌아오면 result.pop()으로 빼서 부모 노드로 되돌아갑니다.
4. 종료 조건: result 길이가 $M$에 도달하면 print(*result)로 출력하고 함수를 종료합니다.

---

💻 코드 구현

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
result = []

def dfs():
    if len(result) == M:
        print(*result)
        return
    
    for i in range(1, N + 1):
        if i not in result:
            result.append(i)
            dfs()
            result.pop()

dfs()

---

🚨 트러블 슈팅 및 회고

• 순열과 조합의 백트래킹 구조 차이: N과 M (2) 문제에서는 start_n 인자를 통해 조합(Combination)을 구현했지만, 이번 문제에서는 인자 없이 in 연산자를 활용해 순열(Permutation)을 구현했습니다. 두 문제의 미세한 코드 차이가 만들어내는 결과물의 차이를 명확하게 이해할 수 있었습니다.
• 방문 처리(Visited) 최적화에 대한 고찰: 현재 코드의 if i not in result:는 $O(M)$의 시간 복잡도를 가집니다. $M$이 최대 8이므로 충분히 빠르고 코드가 직관적이라는 장점이 있습니다. 하지만 만약 $M$이 매우 커진다면, 별도의 visited = [False] * (N+1) 불리언 배열을 만들어 방문 여부를 $O(1)$로 체크하는 방식이 성능 면에서 더 유리할 수 있음을 인지했습니다.

---

💡 [추가 풀이] 파이썬다운 궁극의 1줄 숏코딩: itertools.permutations 활용

백트래킹을 통해 순열의 원리(상태 공간 트리와 방문 처리)를 직접 구현해 보았다면, 실전 코딩 테스트에서는 파이썬의 내장 라이브러리인 itertools.permutations를 활용해 빠르고 정확하게 로직을 전개하는 것이 매우 유리합니다.

이전에 다루었던 combinations(조합)가 오름차순만 유지했다면, 이번 permutations(순열)은 뽑는 순서가 다르면(예: (1, 2)와 (2, 1)) 서로 다른 구성으로 완벽하게 분리하여 반환해 줍니다.

여기에 파이썬의 고급 문법인 제너레이터와 join을 결합하면 DFS 코드를 단 한 줄의 출력문으로 최적화할 수 있습니다.

💻 코드 구현

import sys
from itertools import permutations

input = sys.stdin.readline
N, M = map(int, input().split())

# 순열 생성부터 문자열 변환, 줄바꿈 결합, 출력까지 단 한 줄로 압축
print('\n'.join(' '.join(map(str, p)) for p in permutations(range(1, N + 1), M)))

🔍 1줄 코드 동작 원리 및 I/O 최적화

1. permutations(range(1, N + 1), M): 1부터 N까지의 숫자 중 M개를 뽑아 줄을 세우는 모든 경우의 수(순열)를 차례대로 생성합니다.
2. map(str, p): 생성된 숫자 튜플 안의 정수들을 문자열로 일괄 변환합니다.
3. ' '.join(...): 문자열로 변환된 숫자들을 공백(띄어쓰기)을 기준으로 하나의 문자열로 결합합니다.
4. '\n'.join(... for p in ...): 리스트를 미리 만들지 않고 제너레이터(Generator)를 활용하여, 그때그때 완성된 수열 문자열들을 뽑아낸 뒤 사이사이에 엔터(\n)를 덧발라 거대한 하나의 최종 문자열을 완성합니다.
5. print(...): 여러 번의 출력으로 인한 시간 지연을 막기 위해, 거대하게 완성된 단 하나의 문자열을 딱 한 번만 출력합니다.