[백준][Python] 19699 소-난다!

딱히 소수판별을 체를 사용해서 할 필요는 없을 것 같아서 더한값들 개별적으로 진행해줬다.

조합은 DFS로 구성.

 

import sys
input = sys.stdin.readline

def DFS(start,depth,sum_cow):
    if depth==M:
        if isPrime(sum_cow):
            answer.add(sum_cow)
    for i in range(start,N):
        if not visited[i]:
            visited[i]=True
            DFS(i+1,depth+1,sum_cow+H[i])
            visited[i]=False
            
def isPrime(n):
    if n<2:
        return False
    for i in range(2,n):
        if n%i==0:
            return False
    return True

N,M = map(int,input().split())
H = list(map(int,input().split()))
visited = [False]*N
answer = set()

DFS(0,0,0)

if answer:
    print(*sorted(list(answer)))
else:
    print(-1)