Skip to main content
Talentd

Find the Sum of the Power of All Subsequences - Solution & Explanation

HardArrayDynamic Programming23 min readAsked at: Google, De Shaw
Practice this problem

Problem Statement

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:

  • The subsequence [1,2,3] has 2 subsequences with sum == 3: [1,2,3] and [1,2,3].
  • The subsequence [1,2,3] has 1 subsequence with sum == 3: [1,2,3].
  • The subsequence [1,2,3] has 1 subsequence with sum == 3: [1,2,3].
  • The subsequence [1,2,3] has 1 subsequence with sum == 3: [1,2,3].
  • The subsequence [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:

  • The subsequence [2,3,3] has 2 subsequences with sum == 5: [2,3,3] and [2,3,3].
  • The subsequence [2,3,3] has 1 subsequence with sum == 5: [2,3,3].
  • The subsequence [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 <= 100
  • 1 <= nums[i] <= 104
  • 1 <= k <= 100

Approach Overview

Problem 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 1: Backtracking Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(2^n) - generating all possible subsequences
Space Complexity: O(n) - stack space used by recursion

Try this approach in the editor →

Approach 2: Dynamic Programming Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * k), with n elements and subset sums from 1...k.
Space Complexity: O(k), table reduction enhances memory efficiency.

Try this approach in the editor →

Approach 3: Dynamic Programming

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:

  1. Not in the subsequence S, in which case f[i][j] = f[i-1][j];
  2. In the subsequence S, but not in the subsequence T, in which case f[i][j] = f[i-1][j];
  3. In the subsequence 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 4: Dynamic Programming (Optimization)

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Backtracking Approach

Time Complexity: O(2^n) - generating all possible subsequences
Space Complexity: O(n) - stack space used by recursion

Dynamic Programming Approach

Time Complexity: O(n * k), with n elements and subset sums from 1...k.
Space Complexity: O(k), table reduction enhances memory efficiency.

Dynamic Programming—
Dynamic Programming (Optimization)—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking EnumerationO(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 DPO(n · k)O(k)Preferred in interviews when memory usage matters and DP transitions allow rolling arrays

Video Solution

3082. Find the Sum of the Power of All Subsequences | 0-1 knapsack DP | Binary Exponentiation • Aryan Mittal • 3,062 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Find the Sum of the Power of All Subsequences easy or hard?
Find the Sum of the Power of All Subsequences is classified as a Hard problem. It requires understanding subsequence enumeration, combinatorial counting, and dynamic programming optimization. Many candidates initially attempt brute force before recognizing the subset-sum DP pattern.
Find the Sum of the Power of All Subsequences Python/Java solution
Python and Java implementations typically use dynamic programming with a 1D or 2D DP array for subset sums. Each element updates the DP states in reverse order to avoid reuse within the same iteration. The final answer aggregates contributions for subsequences whose sum equals k.
How to solve Find the Sum of the Power of All Subsequences in O(n · k)?
Use dynamic programming similar to subset sum. Maintain a DP array where dp[s] counts subsequences with sum s while iterating through the array. For each number update sums in reverse order, and accumulate the contribution of subsequences that reach k using powers of two based on remaining elements.
What is the best approach for Find the Sum of the Power of All Subsequences?
The most efficient approach uses dynamic programming over subsequence sums. Track how many subsequences produce each sum while iterating through the array, then compute the power contribution for subsequences that reach sum k. This reduces the exponential subsequence search to roughly O(n · k) time.
Is Find the Sum of the Power of All Subsequences asked at Google/Amazon/Meta?
Problems involving subsequence counting, subset sums, and dynamic programming frequently appear in interviews at companies like Google, Amazon, and Meta. This problem combines subset enumeration with combinatorial counting, which is a common advanced DP interview pattern.
What data structure is used in Find the Sum of the Power of All Subsequences?
The core data structure is a dynamic programming array or table indexed by possible sums. It stores counts of subsequences reaching each sum while processing the array. Precomputed power-of-two arrays are often used to quickly calculate contribution weights.
What is the time complexity of Find the Sum of the Power of All Subsequences?
The brute force backtracking solution runs in O(2^n) time because every subsequence must be generated. The optimized dynamic programming approach runs in O(n · k) time, where n is the array length and k is the target sum. Space complexity ranges from O(k) to O(n · k) depending on the DP design.

Ready to solve this problem?

Practice Find the Sum of the Power of All Subsequences with our built-in code editor and test cases.

Practice on FleetCode
Previous

Number of Subsequences That Satisfy the Given Sum Condition