You are given an integer array nums. A good subsequence is defined as a subsequence of nums where the absolute difference between any two consecutive elements in the subsequence is exactly 1.
Return the sum of all possible good subsequences of nums.
Since the answer may be very large, return it modulo 109 + 7.
Note that a subsequence of size 1 is considered good by definition.
Example 1:
Input: nums = [1,2,1]
Output: 14
Explanation:
[1], [2], [1], [1,2], [2,1], [1,2,1].Example 2:
Input: nums = [3,4,5]
Output: 40
Explanation:
[3], [4], [5], [3,4], [4,5], [3,4,5].
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 105Problem Overview: You are given an integer array and need the total sum of all good subsequences. A subsequence is considered good when the absolute difference between every pair of adjacent elements equals 1. Instead of listing subsequences explicitly, the goal is to efficiently accumulate the sum contributed by every valid subsequence.
Approach 1: Brute Force Enumeration (O(2^n) time, O(n) space)
Generate every subsequence using recursion or bitmasking. For each subsequence, check whether the absolute difference between adjacent elements equals 1. If the subsequence is valid, compute its element sum and add it to the global result. This approach directly follows the definition but quickly becomes impractical because the number of subsequences grows exponentially. It only works for very small arrays and mainly serves as a conceptual baseline.
Approach 2: Dynamic Programming with Hash Map (O(n) time, O(n) space)
The key observation: a good subsequence ending with value x can only extend from subsequences ending with x-1 or x+1. Maintain two hash maps: count[v] for the number of good subsequences ending with value v, and sum[v] for the total sum of all such subsequences. When processing a new element v, create new subsequences in three ways: the single-element subsequence [v], extensions of subsequences ending in v-1, and extensions of those ending in v+1.
When extending a subsequence ending at k, the new sum increases by v. So the contribution from that side becomes sum[k] + count[k] * v. Add contributions from both neighbors and update the maps for value v. Accumulate the newly created sums into the final answer. A hash map ensures constant-time lookups for v-1 and v+1, making the algorithm linear with respect to the array length.
This approach relies on incremental aggregation instead of explicitly building subsequences. Each number only interacts with two neighboring states, which keeps the transitions simple and efficient.
Recommended for interviews: Interviewers expect the dynamic programming solution combined with a hash table. The brute force method demonstrates understanding of subsequences but fails on constraints. The DP transition using neighbor values shows strong reasoning about state compression and works efficiently with arrays of large size.
This approach involves generating all subsequences of the given array and checking if each subsequence is good, i.e., consecutive elements have an absolute difference of 1.
Once we identify a good subsequence, we calculate the sum of its elements. We take care of possible overflows by applying the modulus operation with 10^9 + 7 after every addition.
Though simple, this approach is inefficient for large arrays due to its exponential time complexity.
The code defines a helper function valid_sequence to check if a subsequence is good. Another helper subsequences generates all subsequences of the list recursively. It computes the total sum of elements in all good subsequences and returns it.
Python
JavaScript
Time Complexity: O(2^n * n), where n is the length of the array, due to generating all subsequences. Space Complexity: O(2^n), due to storing all subsequences.
Instead of generating all subsequences, we can opt for a more efficient approach using dynamic programming.
Create a frequency array to count occurrences of each element. Iterate through possible values, updating a dp array, which keeps the sum of all subsequences ending with a particular value.
For each number i, you can either start a subsequence or extend subsequences ending with i-1, i, or i+1, respecting the absolute difference constraint.
Modulo operation ensures we handle large numbers properly.
This Python code utilizes an array dp that stores cumulative subsequences sums ending at each number. We update our dp array based on current frequency and potential pre-existing subsequences.
Time Complexity: O(n + max_value), where max_value is the maximum number in nums. Space Complexity: O(max_value).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(2^n * n), where n is the length of the array, due to generating all subsequences. Space Complexity: O(2^n), due to storing all subsequences. |
| Dynamic Programming Approach | Time Complexity: O(n + max_value), where max_value is the maximum number in nums. Space Complexity: O(max_value). |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(2^n) | O(n) | Understanding the definition of good subsequences or testing small inputs |
| Dynamic Programming with Hash Map | O(n) | O(n) | General case and interview solution where large arrays require efficient aggregation |
3351. Sum of Good Subsequences | DP | Don't Overthink here :) • Aryan Mittal • 4,675 views views
Watch 6 more video solutions →Practice Sum of Good Subsequences with our built-in code editor and test cases.
Practice on FleetCode