백준 15650번 문제 바로가기

combinations을 이용한 풀이

솔직히 이 문제의 가장 쉬운 방법은 itertools에서 combinations을 불러와서 사용하는게 아닐까? 일단 정답 처리는 되었는데 백트래킹을 이용해서 다시 풀어보려고 한다. 백준 15649 - N과 M (1)과 같은 맥락

# 입력
import sys
from itertools import combinations
n,m = map(int, sys.stdin.readline().split())
arr = [i+1 for i in range(n)]

# 처리
for ans in combinations(arr, m):
    print(*list(ans))

backtracking을 이용한 풀이

백준 15649 - N과 M (1)와 비슷하면서도 중복을 허용하지 않기 때문에 가지치기에 고려할게 늘었다. backtrack() 재귀 함수에서 매개변수로 start 숫자를 전달해주면 오름차순으로 쉽게 해결할 수 있다.

# 입력
import sys
n,m = map(int, sys.stdin.readline().split())
ans = []

# 처리
def backtrack(start=1):
    if len(ans) == m:
        print(*list(map(str, ans)))
        return
    for i in range(start, n+1):
        if i not in ans:
            ans.append(i)
            backtrack(i+1)
            ans.pop() # return이 실행되면 여기로 돌아옴. (전 단계로 돌아감 = backtrack)

backtrack()