15652 N과M(4) _python

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

15652번: N과 M (4)

 

12개의 비슷한 문제가 있는 문제 (1)~(12)

 

 

문제 접근

백트래킹

문제를 읽어보면 끝자리를 계속 바꿔나가니 스택으로 접근하기 가장 알맞아보인다.

스택으로 접근하는데 모든경우를 탐색한다는 것은 dfs를 사용하면 쉽게 풀린다.

 

 

 

코드

import sys
input = sys.stdin.readline

"""

"""

N, M = map(int,input().split())
arr = []

def dfs(x):
    if len(arr)==M:
        print(*arr)
        return
    for i in range(x,N+1):
        arr.append(i)
        dfs(i)
        arr.pop()

dfs(1)