Dynamic Programming • 0/1 Knapsack Pattern

Count Subsets with Sum K

Count how many subsets of an array sum up exactly to a target K.

Overview

We want to find the number of ways to pick a subset of elements such that their sum equals K. This is a classic "pick or not pick" DP.

State Definition

Let `dp[i][target]` be the number of subsets using the first `i` elements that sum to `target`.

Transitions

For each element `nums[i]`, we either don't pick it (taking ways from `dp[i-1][target]`), or we do pick it (taking ways from `dp[i-1][target - nums[i]]`).

Key Insight

The total ways is the sum of ways from both decisions: `dp[i][target] = notPick + pick`. Base cases are crucial, especially handling 0s correctly.

Nums:Target Sum:

Num / Target	0	1	2	3
1 (idx 0)	0	0	0	0
2 (idx 1)	0	0	0	0
2 (idx 2)	0	0	0	0
3 (idx 3)	0	0	0	0

Code Tracker

:::

1let dp = Array(n).fill().map(() => Array(sum + 1).fill(0));

2// ... initialize base case for dp[0][s] ...

3for (let i = 1; i < n; i++) {

4 for (let target = 0; target <= sum; target++) {

5 let notPick = dp[i-1][target];

6 let pick = 0;

7 if (target >= nums[i])

8 pick = dp[i-1][target - nums[i]];

9 dp[i][target] = notPick + pick;

10 }

11}

Count Subsets Sum K

Count Subsets Sum K

Count Subsets with Sum K

Overview

State Definition

Transitions

Key Insight

Count Subsets with Sum K

Overview

State Definition

Transitions

Key Insight