15663: N과 M (9)

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

15663번: N과 M (9)

설명

길이가 M인 수열을 모두 구하는 프로그램. N개의 자연수 중에서 M개를 고른 수열.

핵심 아이디어

• 백트래킹
• 중복되는 수열이 없도록 확인하기 위해 remember 변수 활용!

코드 구현

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
data = sorted(list(map(int, input().split())))
# 방문처리로 본인은 다시 선택되지 못하게 한다.
visited = [False] * n
arr = []

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