1146. Subset Sum Problem

Given an array nums of non-negative integers and a target, determine whether any subset sums exactly to the target. Return true or false. The input is JSON {nums, target}.

Input: JSON {nums, target}.

Output: Boolean — true or false.

Examples

Input: {"nums":[3,34,4,12,5,2],"target":9}
Output: true
Explanation: 4+5 = 9.

Input: {"nums":[3,34,4,12,5,2],"target":30}
Output: false
Explanation: No subset sums to 30.

Input: {"nums":[1,2,3],"target":0}
Output: true
Explanation: The empty subset.

Constraints

• 1<=n<=200
• 0<=target<=10^4

Asked by