229. Does a Subset Add Up
Challenge1000 ms256 MBSolved by 0%
Given n positive integers and a target t, print Yes if some subset of
them adds up to exactly t, and No otherwise.
The recursion is the same in-or-out choice as counting subsets: for each number, either use it or skip it, and ask the same question about the rest.
That explores 2^n possibilities, which at n = 30 is a billion. Two things
rescue it. Stop the moment you find an answer rather than exploring the rest.
And stop a branch as soon as the running total passes t, since every number
is positive and it can only grow.
Constraints - `1 ≤ n ≤ 30` - `1 ≤ t ≤ 1000000000` - `1 ≤ a[i] ≤ 100000000`
Input
The first line contains two integers n and t.
The second line contains n positive integers.
Output
Print Yes or No on one line.
Input4 9
3 34 4 12
OutputNo
Notehas no subset reaching the target
Input4 7
3 34 4 12
OutputYes
Noteis 3 + 4, using two of the four values
Hint 1Approach
Hint 2Approach
Hint 3Pseudocode
Hint 4Full solution