Pattern visualizer
Count of Subset Sum
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. Animated on: nums=[1,2,2,3], target=4 — how many subsets sum to exactly 4?.
2-D table of COUNTS: dp[i][j] = dp[i-1][j] (skip) + dp[i-1][j-num] (take), added not chosen
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.
1FUNCTION countSubsetSum(nums, target):2 dp <- table (LENGTH(nums)+1) x (target+1), all 03 dp[0][0] <- 14 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