Can a Subset Reach the Target Sum?

MediumArraysDynamic programming243 tests

You get an array nums of non-negative integers and a non-negative integer target.

Return true if you can pick some of the elements so that their sum is exactly target. Otherwise return false.

Each element can be picked at most once.
You may pick no elements at all. That empty choice has sum 0, so target = 0 is always true.
Two elements with the same value are still two different elements.

Hint

Keep a table of the sums you can already make. Go through the elements one by one. For each element, every sum you could make before can now also grow by that element's value. Walk the sums from high to low so one element is not used twice.

Examples

Example 1

Input:: [6,13,4,9], 19
Output:: true

6 + 13 = 19, so the answer is true. (6 + 4 + 9 = 19 also works.)

Example 2

Input:: [8,10,14], 20
Output:: false

The possible sums are 0, 8, 10, 14, 18, 22, 24 and 32. None of them is 20.

Example 3

Input:: [], 0
Output:: true

There are no elements, but picking nothing gives sum 0, which equals the target.

Constraints

0 <= nums.length <= 15
0 <= nums[i] <= 40
0 <= target <= 700

Run checks your code against the 3 examples. Submit checks it against all 243 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.