문제 요약
자연수 1..N에서 길이가 M인 수열을 모두 출력한다.
- 중복 선택 가능
- 수열은 비내림차순 (A1 ≤ A2 ≤ … ≤ AM)
- 출력은 사전 순 증가
풀이 메모
이 문제는 이전에 풀었던 N과 M 시리즈(2), (3) 와 거의 동일한 백트래킹 구조라서, 이번 포스트에서는 상세 코드 설명은 생략하겠다.
핵심 차이는:
- (3)은 중복 허용 + 순열 형태라서 다음 단계에서도 시작 범위를 그대로 두는 느낌이었다면
- (4)는 중복 허용 + 비내림차순 조건이 있어서, 다음 단계에서 현재 선택한 값 이상만 다시 선택하도록
dfs(x)형태로 내려간다.
내 코드
n, m = map(int, input().split())
path = []
out = []
def dfs(start):
if len(path) == m:
out.append(' '.join(map(str, path)))
return
for x in range(start, n + 1):
path.append(x)
dfs(x)
path.pop()
dfs(1)
print('\n'.join(out))