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.
This approach generates all possible subsets of the input array and calculates their sums. It counts how many subsets have their sum equal to k. This brute-force approach uses recursion and can be optimized with backtracking techniques to avoid entire paths that cannot lead to a viable solution. Due to its computational intensity, this method may not be suited for larger arrays or k values.
The C program employs a recursive backtracking function to explore all possible subsets. For each recursive call, the current element is either included in the subsequence or it is not. If a subsequence's sum reaches k, the count is incremented. The base case terminates recursion when we've considered all elements. A modulo operation keeps count within constraints to prevent integer overflow.
Time Complexity: O(2^n) - generating all possible subsequences
Space Complexity: O(n) - stack space used by recursion
This optimized approach leverages dynamic programming to resolve the problem more efficiently. It uses a DP table where dp[i][j] indicates the number of subsequences using the first i elements of nums with a sum of j. The transition is characterized by using or skipping the current element to reach different state sums. The solution exploits the reduced range from constraint k ≤ 100 to use space effectively.
This C code uses dynamic programming to avoid explicitly enumerating subsets. It iterates over elements with a one-dimensional state array 'dp', capturing feasible sum states. The DP array represents counts incrementally extending through element availability at progressively calculated indices aligned alternately to inclusion.
Time Complexity: O(n * k), with n elements and subset sums from 1...k.
Space Complexity: O(k), table reduction enhances memory efficiency.
The problem requires us to find all subsequences S in the given array nums, and then calculate the number of ways for each subsequence T such that the sum of T equals k.
We define f[i][j] to represent the number of ways to form subsequences with the first i numbers such that the sum of each subsequence equals j. Initially, f[0][0] = 1, and all other positions are 0.
For the i-th number x, there are three cases:
S, in which case f[i][j] = f[i-1][j];S, but not in the subsequence T, in which case f[i][j] = f[i-1][j];S, and in the subsequence T, in which case f[i][j] = f[i-1][j-x].In summary, the state transition equation is:
$
f[i][j] = f[i-1][j] times 2 + f[i-1][j-x]
The final answer is f[n][k].
The time complexity is O(n times k), and the space complexity is O(n times k). Here, n is the length of the array nums, and k$ is the given positive integer.
Python
Java
C++
Go
TypeScript
In the state transition equation from Solution 1, the value of f[i][j] only depends on f[i-1][j] and f[i-1][j-x]. Therefore, we can optimize the first dimension of the space, reducing the space complexity to O(k).
Time complexity is O(n times k), and space complexity is O(k). Here, n is the length of the array nums, and k is the given positive integer.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time Complexity: O(2^n) - generating all possible subsequences |
| Dynamic Programming Approach | Time Complexity: O(n * k), with n elements and subset sums from 1...k. |
| Dynamic Programming | — |
| Dynamic Programming (Optimization) | — |
| 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 |
3082. Find the Sum of the Power of All Subsequences | 0-1 knapsack DP | Binary Exponentiation • Aryan Mittal • 3,021 views views
Watch 7 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