COMP2521

Recursion: Subset Sum

Given n non-negative integers and a target T, decide whether some subset (possibly empty) sums to exactly T.

Classic recursion: for item i, branch take/skip — rec(i+1, sum+a[i]) or rec(i+1, sum); hit when sum==T, stop at i==n.

Input: line 1 n T; line 2 n non-negative integers.
Output: YES or NO.

Example: 4 6 / 1 2 3 7 -> YES (1+2+3).

Samples

stdin

4 6
1 2 3 7

expected

YES

stdin

3 100
1 2 3

expected

NO

c-dcc