DSA Tracker

Visualize

Subset Sum Problem

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

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

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.

Details

Animated on: nums=[3, 4, 5, 2], target=7 — does some subset add up to exactly 7?

Problem:Subset Sum ProblemMedium

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

step 1 / 13

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

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

Every step in words

Show all 13 steps
  1. 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.
  2. Row 0 uses no numbers at all: sum 0 is reachable by taking nothing, every other sum is not. dp[0][0]=T is the only seed the whole table grows from.
  3. Sum 1 is smaller than 3, so this number cannot be part of it. The only edge in is straight down from dp[0][1]=F — the answer is copied, unchanged.
  4. Skipping 3 leaves dp[0][3]=F, but dp[0][0]=T — sum 0 was reachable, so taking 3 reaches 3. Two arrows in, one T is enough.
  5. Row 1 complete. Using 3 the reachable sums are 0, 3 — each one built only from row 0, never from row 1 itself, which is why 3 can't be reused.
  6. Skipping 4 leaves dp[1][4]=F, but dp[1][0]=T — sum 0 was reachable, so taking 4 reaches 4. Two arrows in, one T is enough.
  7. Target hit. dp[1][3]=T says sum 3 was already reachable, so adding 4 lands exactly on 7. Once a cell is T no later row can undo it.
  8. Row 2 complete. Using 3, 4 the reachable sums are 0, 3, 4, 7 — each one built only from row 1, never from row 2 itself, which is why 4 can't be reused.
  9. Skipping 5 leaves dp[2][5]=F, but dp[2][0]=T — sum 0 was reachable, so taking 5 reaches 5. Two arrows in, one T is enough.
  10. Row 3 complete. Using 3, 4, 5 the reachable sums are 0, 3, 4, 5, 7 — each one built only from row 2, never from row 3 itself, which is why 5 can't be reused.
  11. Skipping 2 leaves dp[3][2]=F, but dp[3][0]=T — sum 0 was reachable, so taking 2 reaches 2. Two arrows in, one T is enough.
  12. Row 4 complete. Using 3, 4, 5, 2 the reachable sums are 0, 2, 3, 4, 5, 6, 7 — each one built only from row 3, never from row 4 itself, which is why 2 can't be reused.
  13. Bottom-right cell dp[4][7]=T — with all 4 numbers available, sum 7 is reachable. Walking the T cells back up the arrows recovers the subset itself.

Now solve it yourself

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

Solve Subset Sum Problem in the editorAll Dynamic Programming problemsBack to roadmap