Pattern visualizer

Subset Sum

Each number offers exactly two choices, so every cell has exactly two ways in. dp[i][j] asks 'using only the first i numbers, can I hit sum j?' — and the answer is yes if it was already yes without this number (dp[i-1][j], the arrow straight down) or if sum j-num was reachable and this number closes the gap (dp[i-1][j-num], the arrow from up-left). Both sources sit in the PREVIOUS row, which is what stops a number being spent twice. Row 0 seeds the table with the one thing that needs no numbers at all: sum 0. Animated on: nums=[3, 4, 5, 2], target=7 — does some subset add up to exactly 7?.

2-D table: skip the number (copy down) or take it (jump left by its value)

time O(n * target)space O(n * target)step 1 / 13

dp[i][j] = can the first i numbers hit sum j

01234567

-3452

line 2

5 rows (numbers used so far) by 8 columns (every sum from 0 to 7). Nothing is decided yet — each cell will answer one yes/no question.

Pseudocode

1FUNCTION subsetSum(nums, target):
2  dp <- table (LENGTH(nums)+1) x (target+1), all FALSE
3  dp[0][0] <- TRUE
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 AND dp[i-1][j-num] = TRUE:
9        dp[i][j] <- TRUE
10  RETURN dp[LENGTH(nums)][target]

← / → step · space play · Home restart

Where to practice Dynamic Programming

Practice Dynamic Programming problems All Dynamic Programming problems Back to roadmap