You are given an integer array nums of length n and a positive integer k.
The power of an array of integers is defined as the number of subsequences with their sum equal to k.
Return the sum of power of all subsequences of nums.
Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: nums = [1,2,3], k = 3
Output: 6
Explanation:
There are 5 subsequences of nums with non-zero power:
[1,2,3] has 2 subsequences with sum == 3: [1,2,3] and [1,2,3].[1,2,3] has 1 subsequence with sum == 3: [1,2,3].[1,2,3] has 1 subsequence with sum == 3: [1,2,3].[1,2,3] has 1 subsequence with sum == 3: [1,2,3].[1,2,3] has 1 subsequence with sum == 3: [1,2,3].Hence the answer is 2 + 1 + 1 + 1 + 1 = 6.
Example 2:
Input: nums = [2,3,3], k = 5
Output: 4
Explanation:
There are 3 subsequences of nums with non-zero power:
[2,3,3] has 2 subsequences with sum == 5: [2,3,3] and [2,3,3].[2,3,3] has 1 subsequence with sum == 5: [2,3,3].[2,3,3] has 1 subsequence with sum == 5: [2,3,3].Hence the answer is 2 + 1 + 1 = 4.
Example 3:
Input: nums = [1,2,3], k = 7
Output: 0
Explanation: There exists no subsequence with sum 7. Hence all subsequences of nums have power = 0.
Constraints:
1 <= n <= 1001 <= nums[i] <= 1041 <= k <= 100Solutions for this problem are being prepared.
Try solving it yourselfL6. Recursion on Subsequences | Printing Subsequences • take U forward • 747,428 views views
Watch 9 more video solutions →Practice Find the Sum of the Power of All Subsequences with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor