Total Power Across All Subsequences
Company: Teradata
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
# Total Power Across All Subsequences
You are given an integer array `nums` and a positive integer `k`.
The power of an array is the number of its subsequences whose elements sum to exactly `k`. Return the sum of the powers of every subsequence of `nums`, modulo `10^9 + 7`.
A subsequence is formed by choosing indices in increasing order; the chosen positions need not be contiguous. Choices of different indices are counted separately, even when their value sequences are equal. For each outer subsequence, count its own qualifying inner subsequences in its power.
### Examples
**Example 1**
```text
Input: nums = [1,1,2], k = 2
Output: 6
```
Distinguish the first and second occurrences of one. The outer subsequence containing all three positions has power two: its qualifying inner choices are the pair of ones and the single two. Four other outer choices have power one: the pair of ones, the single two, and each of the two ways to choose one occurrence of one together with the two. All remaining outer choices have power zero. The total is `2 + 1 + 1 + 1 + 1 = 6`.
**Example 2**
```text
Input: nums = [2,2,7], k = 4
Output: 2
```
The pair of twos has power one. The outer subsequence containing all three positions also has power one, because it contains that pair. Every other outer choice has power zero. A value larger than `k` may still belong to an outer subsequence whose power is positive.
### Constraints
- `n == nums.length`.
- `1 <= n <= 100`.
- `1 <= nums[i] <= 10^4`.
- `1 <= k <= 100`.
### Clarifying Questions
- Is power the sum of the subsequence's values? No; it is a count of that subsequence's inner subsequences with sum `k`.
- Are equal-valued elements at different indices distinguishable? Yes; subsequences are selected by indices.
- Must either level of subsequence be contiguous? No.
- Does a number greater than `k` have to be removed from all consideration? No; it cannot occur in a qualifying inner sum, but it can occur in an outer subsequence.
- Can an empty inner subsequence satisfy the target? No, because `k` is positive. An empty outer subsequence likewise has power zero.
### C++ Interface
```cpp
class Solution {
public:
int sumOfPower(vector<int>& nums, int k) {
}
};
```
### Reasoning Checkpoints
- Interpret both levels of subsequence selection and preserve index-based multiplicity.
- Include each qualifying inner choice in the power of every outer choice that contains it.
- Apply the modulus and justify correctness, arithmetic and resource use under the full bounds.
```hint Count nested selections together
Count pairs consisting of an outer subsequence and a qualifying inner subsequence contained in it. At each input index, the element can be outside the outer choice, in the outer choice only, or in both. Track the inner sum.
```
Overview: Sum the powers of every index-selected subsequence, counting its own target-sum subsequences and returning the total modulo one billion and seven.