Number of Subsequences with Odd Sum - Solution & Explanation
Problem Statement
Given an array nums, return the number of subsequences with an odd sum of elements.
Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: nums = [1,1,1]
Output: 4
Explanation:
The odd-sum subsequences are: [1, 1, 1], [1, 1, 1], [1, 1, 1], [1, 1, 1].
Example 2:
Input: nums = [1,2,2]
Output: 4
Explanation:
The odd-sum subsequences are: [1, 2, 2], [1, 2, 2], [1, 2, 2], [1, 2, 2].
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 109
Approach Overview
Problem Overview: Given an integer array, count how many subsequences have an odd sum. A subsequence can skip elements but must keep the original order. The key observation is that the parity of the sum (odd or even) depends only on how many odd numbers are included.
Approach 1: Brute Force Enumeration (O(2^n) time, O(1) space)
Generate every possible subsequence and compute its sum. A bitmask from 0 to 2^n - 1 represents which elements are included. For each mask, iterate through the array, accumulate the sum, and check whether the result is odd. This approach demonstrates the definition of subsequences clearly but becomes impractical once n grows beyond ~20 because the number of subsets doubles with each element.
Approach 2: Dynamic Programming with Parity Tracking (O(n) time, O(1) space)
Track two values while iterating through the array: the number of subsequences with even sum and the number with odd sum. When you see an even number, appending it keeps the parity unchanged. When you see an odd number, appending it flips the parity. Update counts accordingly: new odd subsequences come from extending previous even ones with the odd element, while new even subsequences come from extending previous odd ones. This is a classic dynamic programming pattern where the state only depends on the previous step. The algorithm processes each element once and maintains constant memory.
Approach 3: Combinatorics / Parity Counting (O(n) time, O(1) space)
A subsequence has an odd sum if it contains an odd number of odd elements. Count how many numbers are even (e) and how many are odd (o). Any subset of even numbers can be chosen freely (2^e choices). For odd numbers, you must choose an odd-sized subset, which has 2^(o-1) possibilities when o > 0. Multiply these counts to get the total number of valid subsequences. This reasoning relies on simple combinatorics and parity properties rather than iterative state updates.
Recommended for interviews: The dynamic programming approach is what interviewers typically expect. It shows you understand parity transitions and can model the problem with minimal state. Starting with brute force demonstrates baseline reasoning, but reducing it to an O(n) parity-based DP signals strong algorithmic intuition.
Solution
We define f[0] to represent the number of subsequences with an even sum so far, and f[1] to represent the number of subsequences with an odd sum so far. Initially, f[0] = 0 and f[1] = 0.
Traverse the array nums, for each number x:
If x is odd, the update rules for f[0] and f[1] are:
$
\begin{aligned}
f[0] & = (f[0] + f[1]) bmod 10^9 + 7, \
f[1] & = (f[0] + f[1] + 1) bmod 10^9 + 7.
\end{aligned}
That is, the current number of subsequences with an even sum is equal to the previous number of subsequences with an even sum plus the number of subsequences with an odd sum concatenated with the current number x; the current number of subsequences with an odd sum is equal to the previous number of subsequences with an even sum concatenated with the current number x plus the previous number of subsequences with an odd sum, plus one subsequence containing only the current number x.
If x is even, the update rules for f[0] and f[1] are:
\begin{aligned}
f[0] & = (f[0] + f[0] + 1) bmod 10^9 + 7, \
f[1] & = (f[1] + f[1]) bmod 10^9 + 7.
\end{aligned}
That is, the current number of subsequences with an even sum is equal to the previous number of subsequences with an even sum plus the number of subsequences with an even sum concatenated with the current number x, plus one subsequence containing only the current number x; the current number of subsequences with an odd sum is equal to the previous number of subsequences with an odd sum concatenated with the current number x plus the previous number of subsequences with an odd sum.
Finally, return f[1].
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1)$.
Code
Python
Java
C++
Go
TypeScript
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(2^n) | O(1) | For understanding subsequence generation or when n is very small |
| Dynamic Programming (Parity Tracking) | O(n) | O(1) | General case and most common interview solution |
| Combinatorics Counting | O(n) | O(1) | When you recognize the odd/even parity pattern and want a mathematical shortcut |
Video Solution
Leetcode 1498 - Number of Subsequences That Satisfy the Given Sum Condition - Python • NeetCode • 32,519 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Number of Subsequences with Odd Sum easy or hard?
Number of Subsequences with Odd Sum Python/Java solution
How to solve Number of Subsequences with Odd Sum in O(n)?
What is the best approach for Number of Subsequences with Odd Sum?
Is Number of Subsequences with Odd Sum asked at Google/Amazon/Meta?
What data structure is used in Number of Subsequences with Odd Sum?
What is the time complexity of Number of Subsequences with Odd Sum?
Ready to solve this problem?
Practice Number of Subsequences with Odd Sum with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor