Problem Statement in English

You’re given an array nums, and a target sum k. Your task is to return the power of all subseuences.

The power is defined as the number of subsequences of each subsequence that sums to k.

Approach

Full disclosure: I initially began implementing a brute force solution to this, which actually does make up the brunt of this approach, however, it doesn’t calculate the sum of all possible subsequences within each subsequence that it does calculate.

Didn’t make much sense? Don’t bother, that’s when I realized that I was in way over my head and needed to look up the solution.

I found the solution here, and it took me a fair while to understand what the heck was going on.

I’m going to explain what I understood from the solution. But before that, can we just appreciate how elegant the code is? Wow.

Let’s go over the code piecewise.


return (
                # include index and count towards target
                recursiveCall(index + 1, remaining - nums[index])
                +
                # include index and don't count towards target
                # and exclude index and don't count towards target
                2 * recursiveCall(index + 1, remaining)
            ) % mod

This is the main recursive call that generates subsequences. But there’s actually 3 cases baked into this piece:

  • we include an index in nums and either
    • include it in the subsequence we’re generating, and count it towards the target sum k
    • or, we include it, but don’t count it towards k.
  • we exclude it from the subsequence we’re generating altogether.

Why? You’ll see after the next piece


 if remaining == 0:
                # all the remaining indices in the array
                # can either be chosen or not,
                # 2 choices per remaining index
                return int(pow(2, len(nums) - index)) % mod

If we’ve reached the target k, then we have len(nums) - index to spare in the subsequence, and so we can either choose to use the remaining indices or skip them, which gives us $2$ options per remaining index. Hence $2^\text{len(nums) - index}$. This way we’re not actually generating all the subsequences, but instead just counting them with some math.

And finally, the last piece,


elif index >= len(nums) or remaining < 0:
    return 0

If we’ve exceeded the target, then either

  • the subsequence we’re currently working on doesn’t work, and we can safely discard it, saying that we hit a dead end with no solutions
  • or, we’ve gone out of bounds with respect to the index, and so we’re done generating subsequences down this path, and need to backtrack.

Solution in Python

from functools import cache

class Solution:

    def sumOfPower(self, nums: List[int], k: int) -> int:
        mod = 1_000_000_007

        @cache
        def recursiveCall(index, remaining) -> int:
            # met the target
            if remaining == 0:
                # all the remaining indices in the array
                # can either be chosen or not,
                # 2 choices per remaining index
                return int(pow(2, len(nums) - index)) % mod
            # out of bounds, or target exceeded
            elif index >= len(nums) or remaining < 0:
                return 0

            return (
                # include index and count towards target
                recursiveCall(index + 1, remaining - nums[index])
                +
                # include index and don't count towards target
                # and exclude index and don't count towards target
                2 * recursiveCall(index + 1, remaining)
            ) % mod

        return recursiveCall(0, k)

Complexity

  • Time: $O(n \times \text{?})$
    The $n$ comes from the fact that we’re doing this index wise, but I cannot figure out for the life of me what the $?$ is supposed to be.

  • Space: $O(n \times{k})$
    This is because we’re caching the function signatures, and there can only be $n\times{k}$ calls.

Mistakes I Made

I tried brute forcing this.

And we are done.