문제 출처 : https://www.acmicpc.net/problem/15652

문제 파악

N과 M 문제 (1), (2), (3) 에 이어 (4)이다.

마찬가지로 N과 M이 주어지고
1부터 N까지 자연수 중 M개를 고른 수열을 출력해야 하는데
(4) 문제에서는 같은 수 여러번 골라도 되며,
고른 수열이 '비내림차순' 이어야 한다고 한다.

비내림차순이란 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족해야 한다고 한다.

즉 오름차순 정렬인데, 같은것까진 허용한다는 말이다.

해답 및 풀이

import sys
input = sys.stdin.readline

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

nums = [i+1 for i in range(N)] # [1,2,3..N]

path = []

def backtracking(start):
        # 종료 조건
    if len(path) == M : 
        print(*path)
        return;
    
    # 종료 조건이 아니라면 N번 반복하는데
    for i in range(start, N):
        path.append(nums[i])
        backtracking(i)
        path.pop()
    
backtracking(0)

N과 M (2) 문제와 유사했다.
backtrackgin 함수에 인자로 i를 전달해서
path에 append 하는 반복문에 이 i, 즉 start 를 다시 전달해 i 부터 다시 append 하게끔 하는 기술이 필요했다.

(2) 번과 차이점은 그저 한번 더 진입할 때 인자로 i+1 대신 i 를 넣어 같은 숫자는 허용하는 점에 있었다.