Watch 8 video solutions for Find the Sum of the Power of All Subsequences, a hard level problem involving Array, Dynamic Programming. This walkthrough by Aryan Mittal has 3,021 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 100Problem Overview: You are given an integer array and a target value k. For every subsequence whose elements sum to k, its power depends on how many elements are not chosen. The task is to compute the total power contributed by all such subsequences.
Approach 1: Backtracking Enumeration (O(2^n) time, O(n) space)
This approach generates every possible subsequence using recursive backtracking. At each index you decide whether to include the element or skip it. When a subsequence reaches sum k, compute its contribution using the number of unused elements, typically 2^(n - length), and add it to the result. The recursion explores all 2^n combinations, making it impractical for large inputs but useful for understanding the structure of the problem. This brute‑force exploration highlights that the problem is essentially a subset‑sum variant over an array.
Approach 2: Dynamic Programming on Subsequence Sum (O(n · k) time, O(k) or O(n · k) space)
The optimized solution treats the problem as a variation of subset sum using dynamic programming. Instead of enumerating subsequences, maintain a DP state where dp[s] tracks the number of ways to build subsequences with sum s using processed elements. For each value x in the array, iterate sums backward and update dp[s + x]. To compute the total power, also track the subsequence length or account for remaining elements using precomputed powers of two. After processing all numbers, aggregate contributions of all subsequences with sum k, multiplying each count by 2^(n - length). This converts exponential exploration into polynomial computation.
The key insight is that the power of a valid subsequence depends only on how many elements were excluded, not their positions. Dynamic programming efficiently counts subsequences by sum while implicitly representing many combinations at once. This technique frequently appears in subset counting and knapsack‑style problems involving DP over sums.
Recommended for interviews: Start by explaining the backtracking idea to show you understand how subsequences are formed. Then move to the dynamic programming solution that tracks subsequence sums. Interviewers typically expect the DP optimization because it reduces the exponential search to roughly O(n · k) while keeping memory manageable.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking Enumeration | O(2^n) | O(n) | Small input sizes or when demonstrating the brute-force subsequence generation logic |
| Dynamic Programming (Sum + Length Tracking) | O(n · k) | O(n · k) | General optimized solution when subsequence sums must be counted precisely |
| Space Optimized DP | O(n · k) | O(k) | Preferred in interviews when memory usage matters and DP transitions allow rolling arrays |