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

문제 요약

1부터 N까지의 자연수 중 M개를 중복을 허용하여 고른 수열을 모두 출력

출력은 사전 순으로 증가

각 수열은 한 줄에 출력, 수 사이에는 공백

예시로 살펴보면
입력 3 1이라면,
1부터 3까지 숫자 중 1개를 뽑아 중복 허용 → 가능한 수열: 1, 2, 3
입력 3 2라면,
→ 가능한 수열: 1 1, 1 2, ..., 3 3

필요한 조건
길이가 M인 수열

중복 허용 → visited 체크 X

사전 순 → 항상 1부터 N까지 반복

해결 전략 (백트래킹)

현재 수열이 길이 M이면 출력

아니라면 1부터 N까지 숫자를 넣고 다음 재귀로 넘어가기

중복 허용이므로 visited 체크는 필요 없음

해답 및 풀이

import sys
input = sys.stdin.readline

N, M = map(int, input().strip().split())

result = []

def backtrack():
    if len(result) == M:
        print(' '.join(map(str, result)))
        return

    for i in range(1, N + 1):
        result.append(i)
        backtrack()
        result.pop()

backtrack()