[백준] 15650 | N과 M (2) [파이썬/python]

문제

link: https://www.acmicpc.net/problem/15650

입력받은 값에 따라 조합을 구하는 문제이다.

 

접근

이전에 N과 M (1)을 풀 때 itertools를 사용했기 때문에 이번에는 itertools 대신 백트래킹 알고리즘을 활용해 코드를 작성했다. 재귀함수를 이용했다.

 

코드

import sys
input = sys.stdin.readline

def combination(start):
    if len(tmp) == M:
        print(" ".join(map(str, tmp)))
        return
    
    for i in range(start, N + 1):
        tmp.append(i)
        combination(i + 1)
        tmp.pop()

N, M = map(int, input().split())
tmp = []            
combination(1)

개인적으로 코드를 이해하기 위해 N=3, M=2일 때 코드의 작동 과정을 정리해보았다.