[백준] 15650 : N 과 M (2) (Python/파이썬)

문제 링크

https://www.acmicpc.net/problem/15650

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 
M인 수열을 모두 구하는 프로그램을 작성하시오.

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
고른 수열은 오름차순이어야 한다.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 
중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제

입력

4 2

출력

1 2
1 3
1 4
2 3
2 4
3 4

---

정답 및 풀이

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

def dfs(start):
    if len(arr) == M:
        print(*arr)
        return

    for i in range(start, N + 1):
        arr.append(i)
        dfs(i + 1)
        arr.pop()

dfs(1)

1. N, M = map(int, input().split())
   • 1부터 N까지의 자연수 중에서 M개를 선택하기 위해 N과 M을 입력받는다.
2. arr = []
   • 현재 선택된 숫자들을 저장하는 리스트이며, 재귀 과정에서 값이 추가·제거된다.
3. def dfs(start):
   • 조합을 만들기 위한 재귀 함수이다.
   • start는 다음에 선택할 수 있는 최소 숫자를 의미한다.
4. if len(arr) == M:
   • M개의 숫자를 모두 선택한 경우를 의미한다.
5. print(*arr)
   • 완성된 조합을 공백으로 구분하여 출력한다.
6. return
   • 현재 조합을 출력한 뒤 재귀 호출을 종료한다.
7. for i in range(start, N + 1):
   • start부터 N까지 반복하며 숫자를 하나씩 선택한다.
   • 이를 통해 오름차순이 자동으로 유지된다.
8. arr.append(i)
   • 현재 숫자 i를 조합 리스트에 추가한다.
9. dfs(i + 1)
   • 다음 숫자는 반드시 i보다 큰 값만 선택하도록 하여 중복을 방지한다.
10. arr.pop()
    • 재귀 호출이 끝난 뒤 마지막에 추가한 숫자를 제거한다.
    • 다른 조합을 탐색하기 위한 백트래킹 과정이다.
11. dfs(1)
    • 숫자 1부터 탐색을 시작하여 모든 가능한 조합을 생성한다.

---