1149. Count Subsets with Given Difference

Given an array nums of non-negative integers and a non-negative diff, count the ways to split nums into two subsets S1 and S2 such that sum(S1) - sum(S2) = diff. The input is JSON {nums, diff}.

Input: JSON {nums, diff}.

Output: Integer — the number of such splits.

Examples

Input: {"nums":[1,1,2,3],"diff":1}
Output: 3
Explanation: Three valid splits.

Input: {"nums":[1,2,3,1],"diff":3}
Output: 2
Explanation: Three valid splits.

Input: {"nums":[1],"diff":1}
Output: 1
Explanation: One split.

Constraints

• 1<=n<=100
• 0<=diff<=sum

Asked by