[BOJ][Python] 15650 N과 M (2)

[문제]

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

15650번: N과 M (2)

 

[코드]

15649 N과 M(1) 문제와 다른 점은 다음과 같다. 

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
고른 수열은 오름차순이어야 한다.

 

i 가 재귀를 돌 때마다 1부터 시작하지 않으면 된다. 

함수 인자로 1을 보내주고, 재귀를 돌 때 i + 1을 인자로 보내준다. 

#dfs
x = []
def backtracking(start):
    if len(x) == m:
        print(*x)
        return 
    
    for i in range(start, n+1):
        if visit[i]:
            continue
        visit[i] = True
        x.append(i)
        backtracking(i+1)
        x.pop()
        visit[i] = False
        
#main
import sys
input = sys.stdin.readline

n, m = map(int,input().split())
visit = [False] * (n+1)
backtracking(1)

 

2. 조합 함수로 구현

import sys
input = sys.stdin.readline

from itertools import combinations as c

n, m = map(int,input().split())

arr = [i for i in range(1,n+1)]
x = list(c(arr,m))

for i in x:
    print(*i)