[코딩테스트 공부] N과M (4)

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

문제가 쉬우니까, 코드부터 한 번 보도록하죠

import sys

input = sys.stdin.readline

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

def solution(k, given_length, start_number, partial_sequence):
    if k == given_length:
        print(partial_sequence)
        return
    
    for i in range(start_number, N + 1):
        sequence_param = partial_sequence + str(i) + ' '
        solution(k + 1, given_length, i, sequence_param)
        
solution(0, M, 1, '')

점화 관계만 분석해볼게요

    for i in range(start_number, N + 1):
        sequence_param = partial_sequence + str(i) + ' '
        solution(k + 1, given_length, i, sequence_param)

우리는 숫자의 조합을 고를 때, 다음의 규칙을 가지고 있습니다.

숫자 하나를 고르면, 그 숫자를 포함한 인덱스부터 탐색을 해주면 된다.

따라서, solution 메소드의 파라미터로, start_number에 i를 실어서 보내주면, 재귀함수는 저절로 i 숫자부터 탐색을 시작하게 될 것입니다.