Subset Sum

Given an array of positive integers and a target sum, determine whether there exists a subset whose sum equals the target. This is the classic subset-sum decision problem and a foundational knapsack transformation.

Input Format

nums = array of positive integers, target = required sum

Output Format

true if some subset sums to target, otherwise false

Constraints

• 1 <= nums.length <= 200; 0 <= nums[i] <= 10^4; 0 <= target <= 10^4

Examples

nums = [3,34,4,12,5,2]
target = 9

true

nums = [1,2,3]
target = 7

false