[BOJ] N과 M (4)

---

코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
ans = []

def dfs(start):
    if len(ans) == m:
        print(' '.join(map(str, ans)))
        return
        
    for i in range(start, n+1):
        ans.append(i)
        dfs(i)
        ans.pop()

dfs(1)

결과

풀이 방법

• 백트래킹 문제이다.
• 문제 조건에서 비내림차순(같은 숫자를 여러번 사용하는 것을 허용하는 오름차순) 수열을 요구했기 때문에 현재 추가한 숫자(i) 다음으로 탐색할 숫자의 범위를 range(i, n+1)로 하기 위해 for 문 내에서 dfs(i)를 호출한다.

---