Dynamic Programming • 0/1 Knapsack

Subset Sum

Determine if there is a subset of the given array whose elements sum up to a specific target. This is a foundational 0/1 Knapsack problem.

Try Interactive Simulator

Overview

This asks a simple YES/NO question: Can we pick some elements from the array such that they sum exactly to `target`? It's a classic subset selection problem.

The DP Array

We use a 1D boolean array where `dp[j]` is `true` if a subset with sum `j` exists. It's initialized to `false`, except `dp[0] = true`.

The Transition

For each number `num`, if we can reach sum `j - num`, then we can definitely reach sum `j` by just adding `num`. So, `dp[j] = dp[j] || dp[j - num]`.

Reverse Loop Trap

When compressing from a 2D matrix down to a 1D array, you MUST iterate the inner loop backwards. If you iterate forwards, you might accidentally use the same `num` multiple times!

2

3

7

8

10

DP Array (Can Reach Sum j?)

0

T

1

F

2

F

3

F

4

F

5

F

6

F

7

F

8

F

9

F

10

F

11

F

Code Tracker

:::

1let dp = new Array(target + 1).fill(false);

2dp[0] = true;

3for (let i = 0; i < nums.length; i++) {

4 // Iterate backwards to optimize space to 1D array

5 for (let j = target; j >= nums[i]; j--) {

6 dp[j] = dp[j] || dp[j - nums[i]];

7 }

8}

9return dp[target];