[Python] 백준 15650번 - N과 M (2)

문제 https://www.acmicpc.net/problem/15650

15650번: N과 M (2)

 

n과 m ... 구상하기가 쉽지 않다.

 

n과 m (1) 이랑 비슷한데 (2)에서는 오름차순의 수열만을 골라야 했다.

ex) [1,2]와 [2,1] 중에서 [1,2]만 취급해야 함

 

n과 m (1)에서는 for문을 1 ~ n 까지 다 돌렸었는데

이번에는 for문을 돌릴 때 시작점인 s 변수를 두어 s부터 for문을 돌렸다.

 

이 부분을 생각해내는 게 조금 어려웠고 나머지는 n과 m(1)과 유사하다.

 

import sys
input = sys.stdin.readline

def dfs(s): #s: start
    if len(ans) == m:
        print(*ans)
        return

    for i in range(s, n+1):
        if i not in ans:
            ans.append(i)
            dfs(i+1)
            ans.pop()

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

dfs(1)