백준 15652번: N과 M (4) python

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

문제 접근

1부터 N까지의 숫자들 중 M개를 뽑는데 중복은 허용하되, 크기의 순서가 있게 뽑는 경우의 수를 뽑는 문제.

첫번 째 숫자를 고정하고 백트래킹 알고리즘을 재귀적으로 호출하여 두번째 숫자를 result에 append해주지만 초기값을 start로 주어서 크기의 순서가 있게끔 구현했다.

해답 및 풀이

import sys

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

result = []

def backtrack(start):
    if len(result) == M:
        print(' '.join(map(str, result)))
        return
    
    for i in range(start, N + 1):
        result.append(i)
        backtrack(i)  # i부터 다시 시작해서 중복 허용 + 오름차순 유지
        result.pop()


backtrack(1)