LeetCode 3082 - Find the Sum of the Power of All Subsequences

LeetCode Problem 3082

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming

Solution

Problem Understanding

You are given an array nums and an integer k. For every subsequence of nums, we define its power as the number of subsequences inside it whose sum equals k.

The task is to compute the total power across all subsequences of the original array.

The wording is initially confusing because we are dealing with subsequences inside subsequences. A cleaner way to think about it is this:

• Pick any subsequence S of nums
• Count how many subsequences of S have sum exactly k
• Add that count to the global answer
• Repeat for every possible subsequence S

The final result is the sum of all these counts.

The constraints are important:

• n <= 100
• k <= 100
• nums[i] can be large, but only sums up to k matter

Since n = 100, enumerating all subsequences directly is impossible because there are 2^100 of them.

The small value of k strongly suggests a dynamic programming solution based on subset sums.

An important observation is that we are not simply counting subsequences with sum k. We are summing contributions across all outer subsequences.

For example, if a subsequence T has sum k, then every outer subsequence containing T contributes one count for T.

Suppose T uses m elements. The remaining n - m elements may either be included or excluded independently in the outer subsequence. Therefore:

• Each valid subsequence T contributes 2^(n - m) to the final answer

This transforms the problem into:

For every subsequence with sum k, add 2^(n - length).

That is the key simplification.

Important edge cases include:

• No subsequence sums to k
• Multiple identical values create many distinct subsequences
• k may be smaller than every element
• Large element values greater than k should effectively be ignored in transitions
• Arrays with many zeros are not possible because nums[i] >= 1

Approaches

Brute Force

A brute force solution would generate every subsequence of nums.

For each subsequence S, we would again enumerate all subsequences of S and count how many have sum k.

This is correct because it follows the problem definition directly.

However, the complexity is catastrophic.

There are 2^n subsequences of the original array. For each one, there can again be up to 2^n inner subsequences. The total complexity becomes approximately O(4^n).

With n = 100, this is completely infeasible.

Key Insight

Instead of thinking about outer subsequences first, reverse the perspective.

Consider a subsequence T whose sum equals k.

How many outer subsequences contain T?

If T uses m positions, then each of the remaining n - m positions can independently be included or excluded.

Therefore, T appears inside exactly:

$$2^{n-m}$$

outer subsequences.

So the answer becomes:

$$\sum_{\text{subsequence } T,\ \sum(T)=k} 2^{n-|T|}$$

Now the problem is much easier.

We only need to count subsequences with sum k, weighted by 2^{-length} relative to 2^n.

This naturally leads to dynamic programming.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(4^n)	O(n)	Enumerates all subsequences twice
Optimal DP	O(nk)	O(k)	Dynamic programming over subset sums

Algorithm Walkthrough

Optimal Dynamic Programming

We define:

• dp[s] = weighted count of subsequences with sum s

Initially:

• dp[0] = 1

This represents the empty subsequence.

We process each number one by one.

When adding a number x, every existing subsequence has two choices:

1. Skip x
2. Take x

If we take x, the subsequence length increases by 1.

Recall that each valid subsequence contributes:

$$2^{n-\text{length}}$$

Instead of applying the full factor at the end, we distribute the contribution gradually.

A very elegant recurrence emerges:

When processing a new number:

• Existing subsequences remain unchanged
• New subsequences formed by taking x inherit half the weight

This leads to the transition:

$$newDp[s+x] += dp[s]$$

while every iteration doubles all existing contributions because every outer element can either appear or not appear.

A cleaner implementation uses:

$$dp[j] = 2 \cdot dp[j] + dp[j-x]$$

processed backwards.

Numbered Steps

1. Create a DP array of size k + 1.
2. Set dp[0] = 1 because the empty subsequence has sum 0.
3. Process each number x in nums.
4. Iterate sums backward from k down to 0.
5. For every sum j:

• Double dp[j] because every existing subsequence may either include or exclude the current outer element.
• If j >= x, add dp[j - x] because subsequences summing to j - x can extend with x.

6. Apply modulo arithmetic after every update.
7. After processing all elements, return dp[k].

Why it works

The DP maintains the invariant:

$$dp[s]$$

equals the total contribution of all subsequences with sum s after processing some prefix of the array.

Every new element doubles all existing contributions because each outer subsequence may independently include or exclude the current element.

Additionally, choosing the current element creates new subsequences with larger sums.

Backward iteration prevents reusing the same element multiple times in a single iteration, exactly like standard subset-sum DP.

Thus, every valid subsequence with sum k contributes exactly the correct number of containing outer subsequences.

Python Solution

from typing import List

class Solution:
    def sumOfPower(self, nums: List[int], k: int) -> int:
        MOD = 10**9 + 7
        
        dp = [0] * (k + 1)
        dp[0] = 1
        
        for num in nums:
            new_dp = [0] * (k + 1)
            
            for s in range(k + 1):
                # Exclude current number from subsequence
                new_dp[s] = (new_dp[s] + dp[s] * 2) % MOD
                
                # Include current number
                if s + num <= k:
                    new_dp[s + num] = (new_dp[s + num] + dp[s]) % MOD
            
            dp = new_dp
        
        return dp[k]

The implementation directly follows the mathematical interpretation of the problem.

The array dp[s] stores the total weighted contribution for subsequences whose sum equals s.

At every element:

• Existing contributions are doubled because the current element may or may not appear in the outer subsequence
• We also create new subsequences by including the current element in the inner subsequence

The separate new_dp array avoids accidentally reusing the same element multiple times during a single iteration.

Since only sums up to k matter, the DP size remains small.

All operations are performed modulo 10^9 + 7.

Go Solution

package main

func sumOfPower(nums []int, k int) int {
	const MOD int = 1_000_000_007

	dp := make([]int, k+1)
	dp[0] = 1

	for _, num := range nums {
		newDp := make([]int, k+1)

		for s := 0; s <= k; s++ {
			// Exclude current number
			newDp[s] = (newDp[s] + dp[s]*2) % MOD

			// Include current number
			if s+num <= k {
				newDp[s+num] = (newDp[s+num] + dp[s]) % MOD
			}
		}

		dp = newDp
	}

	return dp[k]
}

The Go implementation mirrors the Python logic closely.

A new DP slice is allocated for every iteration to avoid in-place update issues.

Go uses fixed-width integers, so modulo operations are applied immediately to prevent overflow growth.

Slices are naturally initialized to zero, so no explicit initialization is needed beyond setting dp[0] = 1.

Worked Examples

Example 1

Input:

nums = [1,2,3]
k = 3

Initial state:

Sum	dp
0	1
1	0
2	0
3	0

After processing 1

Sum	Value
0	2
1	1
2	0
3	0

Explanation:

• Existing empty subsequence doubles
• Including 1 creates sum 1

After processing 2

Sum	Value
0	4
1	2
2	2
3	1

Explanation:

• Existing values double
• Adding 2 creates new sums

After processing 3

Sum	Value
0	8
1	4
2	4
3	6

Final answer:

6

Example 2

Input:

nums = [2,3,3]
k = 5

Initial:

Sum	dp
0	1
1	0
2	0
3	0
4	0
5	0

After processing 2

Sum	Value
0	2
2	1

After processing first 3

Sum	Value
0	4
2	2
3	2
5	1

After processing second 3

Sum	Value
0	8
2	4
3	6
5	4

Final answer:

4

Example 3

Input:

nums = [1,2,3]
k = 7

No subsequence can reach sum 7.

Therefore:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(nk)	For each element, we iterate through all sums up to k
Space	O(k)	Only one DP array of size k + 1 is maintained

The algorithm is efficient because k <= 100.

Even with n = 100, the total number of DP transitions is only about 10,000, which is easily manageable.

Test Cases

sol = Solution()

# Provided examples
assert sol.sumOfPower([1,2,3], 3) == 6  # Basic example
assert sol.sumOfPower([2,3,3], 5) == 4  # Duplicate values
assert sol.sumOfPower([1,2,3], 7) == 0  # Impossible target

# Single element equal to k
assert sol.sumOfPower([5], 5) == 1  # One valid subsequence

# Single element not equal to k
assert sol.sumOfPower([5], 3) == 0  # No valid subsequence

# Multiple identical values
assert sol.sumOfPower([1,1,1], 2) == 6  # Multiple combinations

# All elements larger than k
assert sol.sumOfPower([10,20,30], 5) == 0  # Cannot form target

# Larger combination counts
assert sol.sumOfPower([1,1,1,1], 2) == 24  # Many overlapping subsequences

# k equals total sum
assert sol.sumOfPower([1,2,3], 6) == 1  # Only full array works

# Minimum constraints
assert sol.sumOfPower([1], 1) == 1  # Smallest valid input

Test Summary

Test	Why
[1,2,3], k=3	Standard mixed example
[2,3,3], k=5	Duplicate values
[1,2,3], k=7	Impossible target
[5], k=5	Single valid element
[5], k=3	Single invalid element
[1,1,1], k=2	Multiple equivalent subsequences
[10,20,30], k=5	All values exceed target
[1,1,1,1], k=2	Stress repeated combinations
[1,2,3], k=6	Only one full-length subsequence
[1], k=1	Minimum boundary input

Edge Cases

No subsequence sums to k

This is one of the most important cases because many implementations accidentally produce nonzero values due to incorrect initialization or transition ordering.

For example:

nums = [1,2,3]
k = 10

No subset can reach 10, so the answer must remain 0.

The DP handles this naturally because unreachable sums are never updated.

Duplicate numbers

Arrays with repeated values can create many distinct subsequences that have the same numeric contents but use different indices.

For example:

nums = [1,1,1]
k = 2

There are three distinct subsequences producing sum 2.

The DP processes elements positionally, so each occurrence contributes independently and correctly counts all distinct subsequences.

Large values bigger than k

Values larger than k cannot participate in any valid inner subsequence.

For example:

nums = [1000, 2000]
k = 5

A naive implementation might waste time considering impossible transitions.

This solution checks:

if s + num <= k

so impossible sums are skipped immediately.

Full-array target

Sometimes only the entire array achieves the target.

Example:

nums = [1,2,3]
k = 6

Only one subsequence has sum 6.

Its contribution is:

$$2^{3-3} = 1$$

The DP correctly preserves this weighting automatically.