[python] 백준 15663 N과 M (9)

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

15663번: N과 M (9)

문제 해결

입력값에 중복이 있을 수 있지만 출력값 리스트는 중복 허용 X 단 같은 수로 된 리스트는 허용 O

(ex) [1, 2, 2, 3] 입력값에서 [1, 2] 는 한 번 출력 되고 [2, 2] 도 출력 됨 [2,1]도 출력 됨 [1,1] 출력 X

오름차순으로 출력을 하기 때문에 이전 값과 같지 않으면 된다.

이전 값과 리스트의 마지막 값이 같지 않으면 된다. (이를 overlap으로 정의하고 비교를 하자)

visited 로 입력값 원소 하나를 두번이상 사용하는 것을 방지

CODE

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
num = []
visited = [False]*n
def dfs():
    if len(num) == m:
        print(*num)
        return
    overlap = 0
    for i in range(n):
        if not visited[i] and overlap !=A[i]:
            visited[i] = True
            num.append(A[i])
            overlap = A[i]
            dfs()
            visited[i] = False
            num.pop()
        
dfs()