[DP] 부분집합 합

문제

양의 정수 $N$개 $A_0, A_1, \ldots, A_{N-1}$이 주어진다. 이 중 0개 이상을 골라 만든 부분집합의 합이 정확히 $T$가 되게 할 수 있으면 YES, 없으면 NO를 출력하라. 공집합(아무것도 안 고름)의 합은 $0$으로 본다.

접근

$dp[s]$를 "합 $s$를 만들 수 있는가(참/거짓)"로 두고, 각 원소를 한 번씩 보며 갱신한다.

$dp[s] \leftarrow dp[s] \lor dp[s - A_i]$

각 원소를 한 번만 쓰려면 0-1 배낭처럼 안쪽 반복문에서 합 $s$를 큰 쪽에서 작은 쪽으로 내려가며 갱신한다. $dp[0]$은 참으로 시작한다.

입출력 예시

입력:
4 7
3 1 4 2
출력: YES