[백준] 15650 - N과 M (2) (백트래킹, 조합, combinations)

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

15650번: N과 M (2)

from itertools import combinations
from copy import deepcopy
 
n, m = map(int, input().split())
# for comb in combinations(range(1, n + 1), m):
#     for i in comb:
#         print(i, end=' ')
#     print()
#
 
 
def backtracking(comb, index, num):
    if len(comb) == num:
        for i in comb:
            print(i, end=' ')
        print()
    elif len(comb) > n:
        return
 
    for i in range(index, n + 1):
        backtracking(comb[:] + [i], i + 1, num)
 
 
backtracking(list(), 1, m)

백트래킹으로 풀면 된다.

파이썬에서는 간단히 combinations를 사용하면 되는데, 이 문제의 목적은 그 내부적인 로직을 이해하는 것이기 때문에 추가로 직접 구현도 했다.

주석 처리한 부분이 combinations를 이용한 간단 해결법

아래 함수가 백트래킹을 이용해서 직접 구현한 방법이다.