1148. Count Subsets with Given Sum

Given an array nums of non-negative integers and a target, count the number of subsets whose elements sum exactly to the target. The input is JSON {nums, target}.

Input: JSON {nums, target}.

Output: Integer — the number of subsets.

Examples

Input: {"nums":[1,1,1,1],"target":1}
Output: 4
Explanation: Any single 1.

Input: {"nums":[2,3,5],"target":8}
Output: 1
Explanation: 3+5 = 8.

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

Constraints

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

Asked by