Recursion: Subset Sum

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).