783. Count All Subsequences with Given Sum (Modulo 10^9+7)

Given an integer array nums and an integer target, return the number of subsequences (not necessarily contiguous) whose elements sum to exactly target, taken modulo 10^9 + 7. The empty subsequence has sum 0. Elements may be negative. Implement recursively.

Input: An integer array and an integer target: "[a1,...], target".

Output: Return an integer count mod 10^9 + 7.

Examples

Input: [1,2,3], 3
Output: 2
Explanation: Subsequences {3} and {1,2}.

Input: [1,1,1,1,1], 3
Output: 10
Explanation: C(5,3) = 10 ways to pick 3 ones.

Input: [1,2,3], 7
Output: 0
Explanation: Max sum is 6 < 7.

Constraints

• 1 <= nums.length <= 20
• -100 <= nums[i] <= 100
• -1000 <= target <= 1000

Asked by