3082. Find the Sum of the Power of All Subsequences

Problem Description

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 the power of all subsequences of nums.

Since the answer may be very large, return it modulo 10^9 + 7.

Intuition

To solve the problem, we need to efficiently count the number of subsequences that sum up to a given total, k, using dynamic programming.

We define a DP table f[i][j] where f[i][j] represents the number of ways to form subsequences with the first i numbers of the array that result in a sum of j. This approach allows us to break down the problem incrementally by considering each element of the array one by one.

Initially, f[0][0] = 1, as there is exactly one way to achieve a sum of 0 with zero elements—a subsequence containing no elements. For each subsequent element in the array, we have three choices:

Exclude the current element: This keeps the number of ways unchanged for the current sum, i.e., f[i][j] = f[i-1][j].
Include the current element only in subsequences that do not meet the target sum: This again doesn't alter the count for achieving j.
Include the current element in subsequences that meet the target sum: Which means adding the number of ways to achieve the sum j-x where x is the current element. This transition leads us to f[i][j] = f[i-1][j-x].

We adapt our formula to account for doubling the existing subsequences (from the previous element) by multiplying by 2 while adding potential subsequences with the current element included—f[i][j] = f[i-1][j] * 2 + f[i-1][j-x].

By iterating through the list of numbers and updating our DP table in this manner, we finally obtain the desired count modulo 10^9 + 7.

Learn more about Dynamic Programming patterns.

Solution Approach

To solve the problem of finding all subsequences whose sum equals k, we utilize a dynamic programming approach. Here is the step-by-step breakdown of the algorithm:

Initialization: We start by defining a 2D list f where f[i][j] will store the number of ways to get a sum of j using the first i elements of the nums array. Initialize f[0][0] = 1 since there is one way to achieve a sum of 0 with an empty subsequence, and all other values as 0.
Transition: For each element in nums, indexed by i, we consider each possible target sum j from 0 to k:
- If we do not include the current element x (nums[i-1] since the list is 0-indexed but our iteration is 1-indexed) in our subsequence, double the count of ways to reach the current sum j from previous elements: f[i][j] = f[i-1][j] * 2.
- If we choose to include x in subsequences whose sum needs to be equal to j, and if j >= x, adjust the count to reflect these inclusions: f[i][j] = (f[i][j] + f[i-1][j-x]).
Modulo Operation: Since large sums and counts can arise, after computing the possibilities for each state f[i][j], take modulo 10^9 + 7 to ensure the result fits within standard integer limits and adheres to problem constraints: f[i][j] %= 10**9 + 7.
Result Extraction: Finally, the result is stored in f[n][k], which will give us the count of subsequences of nums with sum equal to k.

This dynamic programming table effectively builds up all possible subsequences incrementally, harnessing prior computations to build future ones, reflecting the cumulative sum strategy required by the problem.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example with nums = [1, 2, 3] and k = 3. We'll use the dynamic programming approach described above to find the sum of the power of all subsequences that equal k.

Initialization:
- We create a DP table f where f[i][j] represents the number of ways to form subsequences with the first i numbers from nums that sum up to j.
- Initialize f[0][0] = 1, as there is one way to achieve a sum of 0 with an empty subsequence. All other entries are initially 0.
Filling the DP Table:
- For i = 1 (considering the first number 1):
  - For j = 0, f[1][0] = f[0][0] * 2 = 2.
  - For j = 1, add subsequences including this element: f[1][1] = f[0][1] * 2 + f[0][0] = 0 * 2 + 1 = 1.
  - For j = 2 onward, they remain 0 since 1 alone cannot form those sums.
- For i = 2 (considering the first two numbers 1, 2):
  - For j = 0, f[2][0] = f[1][0] * 2 = 4.
  - For j = 1, f[2][1] = f[1][1] * 2 = 2.
  - For j = 2, add subsequences including 2: f[2][2] = f[1][2] * 2 + f[1][0] = 0 * 2 + 2 = 2.
  - For j = 3, add subsequences including 2: f[2][3] = f[1][3] * 2 + f[1][1] = 0 * 2 + 1 = 1.
- For i = 3 (considering all three numbers 1, 2, 3):
  - For j = 0, f[3][0] = f[2][0] * 2 = 8.
  - For j = 1, f[3][1] = f[2][1] * 2 = 4.
  - For j = 2, f[3][2] = f[2][2] * 2 = 4.
  - For j = 3, account for including 3: f[3][3] = f[2][3] * 2 + f[2][0] = 2 * 2 + 4 = 6.
Modulo Operation:
- Apply modulo 10^9 + 7 at each calculation step, ensuring the integer remains within limits. In this example, results are naturally within bounds.
Result Extraction:
- The desired result is found at f[n][k], which is f[3][3] = 6. Thus, there are 6 subsequences with a sum of 3 in the array [1, 2, 3].

To summarize, this dynamic programming technique efficiently counts the number of subsequences that sum to k by building up from smaller subproblems, thus reducing computational complexity.

Solution Implementation

1from typing import List
2
3class Solution:
4    def sumOfPower(self, nums: List[int], k: int) -> int:
5        # Define the modulus value as per the problem constraints
6        mod = 10**9 + 7
7      
8        # Get the number of elements in the input list 'nums'
9        n = len(nums)
10      
11        # Initialize a 2D list 'f' with (n+1) rows and (k+1) columns filled with zeros
12        # This will be used for dynamic programming to store intermediate results
13        f = [[0] * (k + 1) for _ in range(n + 1)]
14      
15        # Base case: There's one way to sum to 0 - by choosing no elements
16        f[0][0] = 1
17      
18        # Iterate over the elements of the list along with their indices, starting from 1
19        for i, x in enumerate(nums, 1):
20            # Iterate over all possible sum values from 0 to k
21            for j in range(k + 1):
22                # Calculate the number of ways to achieve the sum 'j' using the first 'i' elements
23                f[i][j] = f[i - 1][j] * 2 % mod
24              
25                # If the current sum 'j' is greater than or equal to the current element 'x'
26                if j >= x:
27                    # Include the number of ways to form the sum 'j-x'
28                    f[i][j] = (f[i][j] + f[i - 1][j - x]) % mod
29      
30        # Return the number of ways to form the sum 'k' using all 'n' elements
31        return f[n][k]
32

1class Solution {
2    public int sumOfPower(int[] nums, int k) {
3        final int MOD = (int) 1e9 + 7; // Define the modulo constant
4        int n = nums.length; // Get the length of the nums array
5        int[][] dp = new int[n + 1][k + 1]; // Initialize the dp array for dynamic programming
6        dp[0][0] = 1; // Base case: one way to make sum 0 with no elements
7
8        for (int i = 1; i <= n; ++i) { // Iterate through each element in nums
9            for (int j = 0; j <= k; ++j) { // Iterate over all possible sums up to k
10                // Double the ways to make sum j without including current element
11                dp[i][j] = (dp[i - 1][j] * 2) % MOD;
12              
13                // If current number can be part of the sum
14                if (j >= nums[i - 1]) {
15                    // Add ways to make sum (j - nums[i - 1]) including current element
16                    dp[i][j] = (dp[i][j] + dp[i - 1][j - nums[i - 1]]) % MOD;
17                }
18            }
19        }
20      
21        return dp[n][k]; // Return the number of ways to sum to k using all elements
22    }
23}
24

1#include <vector>
2#include <cstring> // For memset
3
4class Solution {
5public:
6    // This function calculates the sum of powers of subsets of nums that sum to k.
7    int sumOfPower(std::vector<int>& nums, int k) {
8        const int mod = 1e9 + 7; // modulo constant as per problem constraints
9        int n = nums.size(); // number of elements in nums vector
10        int f[n + 1][k + 1]; // Create a 2D array to store intermediate results
11
12        // Initialize all elements of f to 0
13        std::memset(f, 0, sizeof(f));
14
15        // Base case: there's one way to make a sum of 0 (using no elements)
16        f[0][0] = 1; 
17
18        // Iterate over each element in the nums array
19        for (int i = 1; i <= n; ++i) {
20            // Iterate over each possible sum from 0 to k
21            for (int j = 0; j <= k; ++j) {
22                // Without including the current element, double the previous possibilities
23                f[i][j] = (f[i - 1][j] * 2) % mod;
24
25                // If including nums[i - 1] is possible (j >= nums[i - 1]), include those possibilities
26                if (j >= nums[i - 1]) {
27                    f[i][j] = (f[i][j] + f[i - 1][j - nums[i - 1]]) % mod;
28                }
29            }
30        }
31      
32        // The result is the number of ways to make the sum k using all the elements
33        return f[n][k];
34    }
35};
36

1function sumOfPower(nums: number[], k: number): number {
2    // Define modulus to prevent overflow due to large numbers
3    const mod = 10 ** 9 + 7;
4  
5    // Length of the input array 'nums'
6    const n = nums.length;
7  
8    // Create a 2D array `f` of size (n+1)x(k+1) initialized with zeros
9    // `f[i][j]` represents the number of ways to make sum `j` using the first `i` elements of `nums`
10    const f: number[][] = Array.from({ length: n + 1 }, () => Array(k + 1).fill(0));
11  
12    // Base case: There is one way to get a sum of zero using zero elements (empty subset)
13    f[0][0] = 1;
14  
15    // Iterate through each element in `nums`
16    for (let i = 1; i <= n; ++i) {
17        // Iterate through each possible sum from `0` to `k`
18        for (let j = 0; j <= k; ++j) {
19            // Case 1: Don't use the current element, so, carry over the previous count doubled (as the set can include or exclude the element)
20            f[i][j] = (f[i - 1][j] * 2) % mod;
21          
22            // Case 2: Use the current element, if the sum can accommodate it
23            // Add ways to achieve `j` by using one instance of `nums[i-1]`
24            if (j >= nums[i - 1]) {
25                f[i][j] = (f[i][j] + f[i - 1][j - nums[i - 1]]) % mod;
26            }
27        }
28    }
29  
30    // Return the number of ways to achieve sum `k` using all `n` elements of `nums`
31    return f[n][k];
32}
33

Time and Space Complexity

The time complexity of the code is O(n * k). This results from the nested loops where the outer loop runs over n + 1 iterations, corresponding to the number of elements in nums, and the inner loop runs k + 1 times for each value, corresponding to the provided integer k.

The space complexity is O(n * k) due to the 2D list f, which has dimensions (n + 1) x (k + 1). This matrix stores intermediate results for subproblems in the dynamic programming solution.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Topological Sort

Uniform Cost Search

Monotonic Stack

Memoization

I don’t know