15666: N과 M(12)

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

15666번: N과 M (12)

설명

핵심 아이디어

• 백트래킹
• 같은 수를 여러 번 골라도 된다. 방문처리 안해도 된다.
• 고른 수열은 비 내림차순이어야 한다.
• 비 내림 차순으로 풀기 위해서 start 변수를 넣어준다. 

코드 구현

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
data = sorted(list(map(int, input().split())))
arr = []

def dfs(start):
	if len(arr) == m:
		print(*arr)
		return
	else:
		# 이 변수로 중복되는 수열이 나오지 않도록 구현
		remember = 0
		for i in range(start, n):
			if remember != data[i]:
				arr.append(data[i])
				# 중복되는 수열이 없도록 하기 위함
				remember = data[i]
				dfs(i)
				arr.pop()
dfs(0)