iTechGuides is reader-supported. When you buy through links on our site, we may earn an affiliate commission. As an Amazon Associate I earn from qualifying purchases. Learn more
To count subsets whose elements sum to an exact target, keep a count for each array prefix and each sum. When an element fits, add the count that excludes it to the count that includes it. The distinction between counting, checking whether a sum is possible, and maximizing value comes down to what each DP state stores and how its choices are combined.
What the problem asks
Given an array and a target sum, count how many subsets have elements that add to exactly that target. Each array element is considered once: a subset either includes that element or excludes it. Equal-valued elements at different positions are distinct choices, so they can produce different subsets.
| # | Preview | Product | Price | |
|---|---|---|---|---|
| 1 |
|
Dynamic Programming and Optimal Control: Approximate Dynamic Programming | $89.00 | Buy on Amazon |
| 2 |
|
Dynamic Programming and Optimal Control | $89.00 | Buy on Amazon |
| 3 |
|
Dynamic Programming | $45.24 | Buy on Amazon |
| 4 |
|
Dynamic Programming and Optimal Control | $134.50 | Buy on Amazon |
| 5 |
|
Dynamic Programming (Dover Books on Computer Science) | $15.79 | Buy on Amazon |
For [2, 3, 5] with target 5, the subsets are [5] and [2, 3], giving a count of 2.
Define the dynamic programming state
Let T[i][j] be the number of subsets that sum to j using only the first i elements. With an array of length n, the answer is T[n][target].
For the next element, there are two possibilities: exclude it, keeping the prior count for the same sum, or include it, using subsets that made up the remaining sum. If the element fits within j, the recurrence is:
T[i][j] = T[i - 1][j] + T[i - 1][j - arr[i - 1]]
If it is greater than j, it cannot be included, so:
T[i][j] = T[i - 1][j]
Initialize the table correctly
T[0][0] = 1: with no elements, the empty subset is one way to make sum zero.T[0][j] = 0for every positive sumj: no elements cannot make a positive sum.- For each array element, calculate sums starting at zero so the same recurrence also handles zero-valued elements.
Do not initialize every T[i][0] to one. That would miss additional subsets formed by including or excluding zeros.
Why zeros double the count
A zero can be excluded or included without changing a subset’s sum. Those are two distinct choices, so each zero doubles the number of subsets for any sum that was already reachable, including zero. The recurrence handles this naturally: for a zero, the include and exclude terms refer to the same previous sum and are added.
Rank #3
- For
[0]and target0, the subsets are[]and[0], so the count is2. - For
[0, 0]and target0, there are four subsets:[], each single zero, and both zeros.
How counting differs from related DP problems
The recurrence’s structure can look familiar, but the value stored in a state determines how the alternatives are combined.
| Problem | What a state stores | How alternatives combine |
|---|---|---|
| 0/1 knapsack | Maximum value | Take the maximum |
| Subset-sum feasibility | Whether a sum is possible | Logical OR |
| Count of subsets | Number of ways to make a sum | Add the counts |
For subset-sum feasibility, a single valid subset is enough to answer “yes.” For counting, every valid subset contributes to the total, so the include and exclude cases must be added rather than merged into a Boolean result.
Rank #4
- Used Book in Good Condition
Bottom-up implementation in Python
This implementation builds the two-dimensional table directly from the state definition:
def count_subsets(arr, target):
n = len(arr)
dp = [[0] * (target + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
value = arr[i - 1]
for total in range(target + 1):
dp[i][total] = dp[i - 1][total]
if value <= total:
dp[i][total] += dp[i - 1][total - value]
return dp[n][target]The loop starts at total zero, which is important when value is zero: both terms are counted, doubling the ways for that sum. The table uses (n + 1) × (target + 1) integer entries, and the nested loops take O(n × target) time.
Best Value
Memoized recursive version
The same include/exclude recurrence can be written recursively. A distinct marker such as None must represent an uncomputed state, because zero is a valid computed count.
def count_subsets_memo(arr, target):
n = len(arr)
memo = [[None] * (target + 1) for _ in range(n + 1)]
def solve(i, total):
if i == 0:
return 1 if total == 0 else 0
if memo[i][total] is not None:
return memo[i][total]
value = arr[i - 1]
ways = solve(i - 1, total)
if value <= total:
ways += solve(i - 1, total - value)
memo[i][total] = ways
return ways
return solve(n, target)Using 0 as the “not computed” marker would cause states whose actual count is zero to be recomputed instead of recognized as cached.
Check the result on a small example
For [2, 3, 5] and target 5, the final state counts two subsets: [5] and [2, 3]. If the array instead contains zeros, their include/exclude choices are counted as separate subsets by the same recurrence.
Source
The recurrence and examples here follow the instructional explanation in Nishant Gaurav’s DEV Community article, “Count of Subsets: One Word Changed. Everything Followed.”
Quick Recap
Product prices and availability are accurate as of the date/time indicated and are subject to change. Any price and availability information displayed on Amazon at the time of purchase will apply.
