[Algorithm🧬] 더하기

문제

덧셈을 못하는 철수를 공부시키기 위해 자연수들을 주고, 그 중에 몇 개의 수를 골라서 그 합이 K가 될 수 있는지 알아보라고 시켰다.
철수 어머니가 자연수들을 무작위로 선택해서 본인도 가능한지 아닌지 모르고 있다. 어머니가 채점을 할 수 있게 주어진 문제의 답을 찾아주자.

입력

첫 번째 줄에 테스트 케이스 개수 T(1≤T≤10)가 주어진다.
두 번째 줄부터 아래 내용이 T개 만큼 주어진다.
첫 줄에 자연수 개수 N(5 <= N <= 20)과 K(1 <= K <= 2,000,000)가 공백으로 구분되어 입력된다.
다음 줄에 N개의 자연수 di(1 <= di <= 100,000)가 공백으로 구분되어 입력된다.

입력 예시
2
5 19
1 2 4 7 10
5 25
1 2 4 7 10

출력

T줄에 걸쳐 각 테스트 케이스 별로 주어진 자연수 중 몇 개의 합이 K가 되면 “YES”를 아니면 “NO”를 출력한다.

출력 예시
YES
NO

풀이

sum 을 이용해서 지금까지 더한게 크면 DFS 가지로 더 들어갈 필요가 없고
같으면 문제 조건에 맞으니 YES 를 출력
작으면 다른걸 더 더해보는 방식으로 진행했는데
Output Limit Exceed 가 났다.....

그래서 안에서 찍지 않고 바깥에서 찍는 것으로 바꾸었더니.. 됐다... K 가 되는 경우가 여러개 있을 때 문제가 생기는듯...?

import sys

def DFS(level, sum, start):
    global yes

    if level == N:
        if sum == K:
            yes = 1
            # print("YES")
        return

    if sum > K:
        return

    if sum == K:
        yes = 1
        # print("YES")
        return

    if sum < K:
        # start 도 따로 주면 앞의 것을 따로 저장해서 if 문 처리를 할 필요가 없는거였다.
        for i in range(start, N):
            res[level] = nums[i]
            DFS(level + 1, sum + nums[i], i + 1)


T = int(sys.stdin.readline())
for i in range(T):
    N, K = map(int, sys.stdin.readline().split())
    nums = list(map(int, sys.stdin.readline().split()))

    res = [0] * N

    yes = 0
    DFS(0, 0, 0)

    # if yes == 0:
        # print("NO")
    print("YES" if yes == 1 else "NO")