algorithm'''problem solve
[백준] 15650 - N과 M (2) (백트래킹, 조합, combinations)
JunHwa Park
2020. 10. 23. 20:53
https://www.acmicpc.net/problem/15650
15650번: N과 M (2)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
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)
|
cs |
백트래킹으로 풀면 된다.
파이썬에서는 간단히 combinations를 사용하면 되는데, 이 문제의 목적은 그 내부적인 로직을 이해하는 것이기 때문에 추가로 직접 구현도 했다.
주석 처리한 부분이 combinations를 이용한 간단 해결법
아래 함수가 백트래킹을 이용해서 직접 구현한 방법이다.