[백준][Python] 15652번 N과 M (4) - 파이썬

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

15652번: N과 M (4)

풀이

백트래킹을 사용하여서 중복조합을 구현해주면 되는 문제입니다.

백트래킹을 구현하기 위해서는 재귀함수를 사용해줘야합니다. 재귀함수 호출 구문과  재귀함수 종료 구문을 잘 만들어놔야합니다.

# 15652 N과 M (4)
import sys
sys.setrecursionlimit(10000)

N, M = map(int, input().split())
ans =[]
def print_ans():
    sys.stdout.write(f'{" ".join(map(str, ans))}\n')

def choose_num(num, cnt):
    # 재귀함수의 종료조건
    if num == M+1:
        print_ans()
        return
    # 재귀함수의 호출
    for i in range(cnt, N+1):
        ans.append(i)
        choose_num(num + 1, i)
        ans.pop()
    return

choose_num(1, 1)

출력결과