[BOJ] 15664번 N과 M (10) 문제

www.acmicpc.net/problem/15664

15664번: N과 M (10)

 

꽤나 곤란했던 문제다.

 

2번 예시 처럼

 

9 7 9 1이 주어졌을 때, 9가 두개라서 9 9가 나타나지만 1 9 는 한번만 나타나야 한다.

 

따라서 overlap 이라는 변수를 통해서 해당 depth 에서 그 수를 사용했는지 안했는지를 구분했다.

 

어차피 정렬이 되어있기 때문에, 같은 수가 중복 사용되는 경우는 다 걸러 낼 수 있다.

 

 

N, M = map(int, input().split())

numbers = list(map(int, input().split()))
numbers.sort()

visited = [0] * N
element = []
def dfs(depth):

    if depth == M:
        print(*element)
        return

    overlap = 0
    for i in range(depth, N):
        if not element:
            if numbers[i] != overlap:
                element.append(numbers[i])
                visited[i] = 1
                overlap = numbers[i]
                dfs(depth+1)
                element.pop()
                visited[i] = 0
        else:
            if numbers[i] >= element[-1] and visited[i] == 0 and numbers[i] != overlap:
                element.append(numbers[i])
                visited[i] = 1
                overlap = numbers[i]
                dfs(depth+1)
                element.pop()
                visited[i] = 0

dfs(0)