[BaekJoon] 백준 15657번 : N과 M (8)

15657번 : N과 M (8)

[BaekJoon] 백준 15654번 : N과 M (5) 와 같은 백트래킹을 사용하는 문제이다.

15654번 문제와 같지만 순서가 없고 같은 숫자도 뽑을 수있게 풀면 된다.

---

import sys


def DFS():
	global n, m, data, stack

	if len(stack) == m:
		print(*stack)
		return

	for i in range(n):
		if stack and stack[-1] > data[i]:
			continue

		stack.append(data[i])
		DFS()
		stack.pop()


n, m = map(int, sys.stdin.readline().rsplit())
data = sorted(list(map(int, sys.stdin.readline().rsplit())))
stack = []
DFS()

---

import sys
from itertools import combinations_with_replacement


n, m = map(int, sys.stdin.readline().rsplit())
data = sorted(list(map(int, sys.stdin.readline().rsplit())))
res = combinations_with_replacement(data, m)

for val in res:
	print(*val)

기본적으로 조합이지만 자기 자신도 중복을 뽑을 수 있기 때문에 combination_with_replacement 를 사용해도 된다.