DSA Tracker

Visualize

Count Subsets with Sum

2-D table of COUNTS: dp[i][j] = dp[i-1][j] (skip) + dp[i-1][j-num] (take), added not chosen

time O(n * target)space O(n * target)

This is Subset Sum's yes/no question turned into a count: dp[i][j] is not 'can the first i numbers reach sum j' but 'in how many ways'. Every cell still has exactly two arrows in — skip this number (straight down) or take it (up-and-left by its value) — but now BOTH can contribute, and their counts are ADDED, because a subset that skips this number and a subset that takes it are always different subsets. Row 0 seeds the table with the one count that needs no numbers at all: there is exactly 1 way to make sum 0, the empty subset.

Details

Animated on: nums=[1,2,2,3], target=4 — how many subsets sum to exactly 4?

Problem:Count Subsets with SumMedium

2-D table of COUNTS: dp[i][j] = dp[i-1][j] (skip) + dp[i-1][j-num] (take), added not chosen

step 1 / 10

dp[i][j] = # subsets of the first i numbers summing to j

5 rows (numbers used so far) by 5 columns (every sum from 0 to 4). Every cell will count subsets, not just say yes/no.

Pseudocode
1FUNCTION countSubsetSum(nums, target):
2  dp <- table (LENGTH(nums)+1) x (target+1), all 0
3  dp[0][0] <- 1
4  FOR i FROM 1 TO LENGTH(nums):
5    num <- nums[i-1]
6    FOR j FROM 0 TO target:
7      dp[i][j] <- dp[i-1][j]
8      IF j >= num:
9        dp[i][j] <- dp[i][j] + dp[i-1][j-num]
10  RETURN dp[LENGTH(nums)][target]

← / → step · space play · Home restart

Every step in words

Show all 10 steps
  1. 5 rows (numbers used so far) by 5 columns (every sum from 0 to 4). Every cell will count subsets, not just say yes/no.
  2. Row 0 uses no numbers at all: there is exactly 1 way to reach sum 0 — the empty subset — and 0 ways to reach anything else. dp[0][0]=1 is the seed the whole table grows from.
  3. Row 1 complete. Using 1, the counts across every sum come only from row 0 — never from row 1 itself, which is why 1 is never used twice in one subset.
  4. Row 2 complete. Using 1, 2, the counts across every sum come only from row 1 — never from row 2 itself, which is why 2 is never used twice in one subset.
  5. Two arrows both count here: 1 subset(s) already reached 2 without this 2, and 1 subset(s) reached 0 and can take it. dp[3][2] = 1 + 1 = 2.
  6. Row 3 complete. Using 1, 2, 2, the counts across every sum come only from row 2 — never from row 3 itself, which is why 2 is never used twice in one subset.
  7. Two arrows both count here: 2 subset(s) already reached 3 without this 3, and 1 subset(s) reached 0 and can take it. dp[4][3] = 2 + 1 = 3.
  8. Target hit. dp[4][4] = dp[3][4] + dp[3][1] = 1 + 1 = 2 — subsets that skip this 3 plus subsets that take it, added together, not chosen between.
  9. Row 4 complete. Using 1, 2, 2, 3, the counts across every sum come only from row 3 — never from row 4 itself, which is why 3 is never used twice in one subset.
  10. Bottom-right cell dp[4][4] = 2 — with all 4 numbers available, exactly 2 subsets sum to 4.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Count Subsets with Sum in the editorAll Dynamic Programming problemsBack to roadmap