Knapsack: Practice Problems from Subset Sum to Coin Change
Welcome to the practice problems for the knapsack pattern. If you need a refresher on the code, the code templates have the pattern in all 6 languages. Each problem below includes a hint, a visual walkthrough, and the full solution.
Recommended Study Order
Knapsack problems on LeetCode all sit at Medium or above, because even the simplest formulation has an exponential brute force. Treat Partition Equal Subset Sum as the entry point: it teaches the subset sum reduction with the fewest moving parts. Coin Change adds minimization with unlimited reuse, and Coin Change II flips the same table into counting combinations. Target Sum shows the pattern hiding inside a plus and minus sign expression. Ones and Zeroes adds a second budget dimension. Profitable Schemes is the Hard: two constraints, counting, and a cap on the profit dimension so the table stays small.
Medium Problems
1. Partition Equal Subset Sum
LeetCode 416 | Difficulty: Medium
Brief: Given an integer array, decide whether it can be split into two subsets with equal sums.
Why this pattern: Each half must sum to total / 2, so the problem reduces to one question: does a subset summing to total / 2 exist? That is subset sum, which is 0/1 knapsack with the weights doubled as the values.
Key Insight: Check that the total is even first. An odd total can never split into two integer halves, and checking it before building the table avoids a wasted pass.
Visual:
graph LR
A["nums: [1,5,11,5]"] --> B["total = 22, target = 11"]
B --> C["dp[0] = true"]
C --> D["after 1: dp[1] = true"]
D --> E["after 5: dp[5], dp[6] = true"]
E --> F["after 11: dp[11] = true"]
F --> G["return true"]
Code:
var canPartition = function(nums) {
const total = nums.reduce((a, b) => a + b, 0);
if (total % 2 !== 0) return false;
const target = total / 2;
const dp = new Array(target + 1).fill(false);
dp[0] = true; // the empty subset sums to zero
for (const num of nums) {
// Backward loop keeps each number usable once.
for (let s = target; s >= num; s--) {
dp[s] = dp[s] || dp[s - num];
}
}
return dp[target];
};The boolean table reads exactly like the knapsack template with the values removed. The backward loop is the detail to protect. With a forward loop, dp[s - num] may have just been updated by the same number, which would let one number fill both halves of the partition.
Time Complexity:
2. Coin Change
LeetCode 322 | Difficulty: Medium
Brief: Given coin denominations and an amount, return the fewest coins needed to make that amount, or -1 if it is impossible.
Why this pattern: Coins can be reused freely, so this is the unbounded knapsack in minimize form. The table stores the smallest coin count for each amount instead of the best value.
Key Insight: Seed dp[0] = 0 and every other cell with a value larger than any possible answer, such as amount + 1. A cell that never improves stays at the sentinel, which is how you detect impossibility at the end.
Visual:
graph LR
A["amount = 11, coins = [1,2,5]"] --> B["dp[0] = 0"]
B --> C["dp[1] = 1"]
C --> D["dp[2] = 1"]
D --> E["dp[5] = 1"]
E --> F["dp[10] = 2"]
F --> G["dp[11] = 3"]
G --> H["return 3: 5 + 5 + 1"]
Code:
var coinChange = function(coins, amount) {
const dp = new Array(amount + 1).fill(amount + 1);
dp[0] = 0;
for (let a = 1; a <= amount; a++) {
for (const coin of coins) {
if (coin <= a) {
dp[a] = Math.min(dp[a], dp[a - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
};Iterating amounts on the outside and coins inside works here because the minimum is order-independent. The sentinel amount + 1 does double duty. It lets min work without an infinity check on every cell, and a surviving sentinel at the end means no combination of coins reaches the amount.
Time Complexity:
3. Coin Change II
LeetCode 518 | Difficulty: Medium
Brief: Given coin denominations and an amount, return the number of combinations of coins that make that amount.
Why this pattern: This is the unbounded knapsack in counting form. The coin loop on the outside is what makes the answer a combination count instead of a permutation count.
Key Insight: dp[0] = 1 because there is exactly one way to make zero, which is to pick nothing. Iterate coins on the outside so each coin is “introduced” once; iterating amounts on the outside would count 1+2 and 2+1 as different orders.
Visual:
graph LR
A["amount = 5, coins = [1,2,5]"] --> B["dp[0] = 1"]
B --> C["after coin 1: 1 way for every amount"]
C --> D["after coin 2: dp[5] = 3"]
D --> E["after coin 5: dp[5] = 4"]
E --> F["return 4"]
Code:
var change = function(amount, coins) {
const dp = new Array(amount + 1).fill(0);
dp[0] = 1; // one way to make zero: pick no coins
for (const coin of coins) {
// Forward loop, so a coin can be added to sums that
// already used the same coin in this pass.
for (let a = coin; a <= amount; a++) {
dp[a] += dp[a - coin];
}
}
return dp[amount];
};The loop order is the whole problem. With coins on the outside, the coins themselves form the sequence, so 1+2 and 2+1 collapse into one combination. This is the cleanest demonstration of why the unbounded variant walks forward. The same coin feeds the sums it already built.
Time Complexity:
4. Target Sum
LeetCode 494 | Difficulty: Medium
Brief: Given an integer array and a target, assign a plus or minus sign to every number and count the expressions that equal the target.
Why this pattern: The numbers assigned a plus sign form a subset with a fixed sum. If that sum is S, then S - (total - S) = target, so S = (total + target) / 2. The problem becomes counting the subsets that sum to S.
Key Insight: Two checks come before any DP. If |target| > total, no sign assignment can reach it. If (total + target) is odd, S is not an integer and the answer is zero. After that, count subsets summing to S with the standard counting table.
Visual:
graph LR
A["nums: [1,1,1,1,1], target = 3"] --> B["total = 5, subset target = 4"]
B --> C["dp[0] = 1"]
C --> D["count subsets summing to 4"]
D --> E["choose any 4 of the 5 ones"]
E --> F["return 5"]
Code:
var findTargetSumWays = function(nums, target) {
const total = nums.reduce((a, b) => a + b, 0);
if (Math.abs(target) > total || (total + target) % 2 !== 0) return 0;
const sum = (total + target) / 2;
const dp = new Array(sum + 1).fill(0);
dp[0] = 1; // the empty subset is the only way to reach zero
for (const num of nums) {
// Backward loop keeps each number usable once.
for (let s = sum; s >= num; s--) {
dp[s] += dp[s - num];
}
}
return dp[sum];
};This problem is the reason the feasibility checks matter. Without the parity check, a fractional sumNeeded would silently round down and count the wrong subsets. The counting table is the subset sum table from Partition Equal Subset Sum with booleans replaced by integer counts.
Time Complexity:
5. Ones and Zeroes
LeetCode 474 | Difficulty: Medium
Brief: Given binary strings and two budgets, m zeros and n ones, return the largest subset of strings whose combined counts fit both budgets.
Why this pattern: Every string is an item with two weights, one for zeros and one for ones. The DP table gains a second dimension, one column per budget, and each string is still used at most once.
Key Insight: Walk both budget dimensions backward, just like the single-dimension 0/1 knapsack. The value of every item is 1, since the goal is the largest subset, so the transition adds one to the best count for the remaining budgets.
Visual:
graph LR
A["strs: 10, 0001, 111001, 1, 0"] --> B["m = 5 zeros, n = 3 ones"]
B --> C["pick 10, 0001, 1, 0"]
C --> D["zeros: 1 + 3 + 0 + 1 = 5"]
C --> E["ones: 1 + 1 + 1 + 0 = 3"]
D --> F["111001 needs 4 ones, skipped"]
E --> F
F --> G["return 4"]
Code:
var findMaxForm = function(strs, m, n) {
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
for (const s of strs) {
let zeros = 0;
for (const ch of s) {
if (ch === '0') zeros++;
}
const ones = s.length - zeros;
// Walk both budgets backward so each string is used once.
for (let i = m; i >= zeros; i--) {
for (let j = n; j >= ones; j--) {
dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
}
}
}
return dp[m][n];
};The two nested backward loops are the same “one use per item” rule applied in two dimensions. This is also why the problem is the natural bridge to the Hard below. The profit dimension of Profitable Schemes behaves like a second budget, except it has a cap instead of a hard limit.
Time Complexity:
Hard Problems
6. Profitable Schemes
LeetCode 879 | Difficulty: Hard
Brief: Given a member budget n, a profit threshold minProfit, and a list of crimes with a member cost and a profit each, count the subsets of crimes whose total profit is at least minProfit and whose member cost is at most n.
Why this pattern: Every crime is an item with one weight, its member cost, and one value, its profit. The twist is the profit constraint runs in the “at least” direction, which lets you cap the profit dimension at minProfit instead of tracking every higher value.
Key Insight: Any profit above minProfit is equivalent for counting, so store it all at the minProfit column. The final answer is the sum of the minProfit column across all member counts. Counts get large, so every addition applies the modulo.
Visual:
graph LR
A["n = 5 members, minProfit = 3"] --> B["crime 0: 2 members, 2 profit"]
B --> C["crime 1: 2 members, 3 profit"]
C --> D["scheme 1: crime 1 alone"]
C --> E["scheme 2: crime 0 + crime 1"]
D --> F["3 profit, 2 members"]
E --> G["5 profit, 4 members"]
F --> H["return 2"]
Code:
var profitableSchemes = function(n, minProfit, group, profit) {
const MOD = 1000000007;
// dp[members][p] is the number of schemes using exactly
// members people and earning p profit, where any profit
// above minProfit is stored at the minProfit column.
const dp = Array.from({ length: n + 1 }, () => new Array(minProfit + 1).fill(0));
dp[0][0] = 1;
for (let i = 0; i < group.length; i++) {
const g = group[i], p = profit[i];
// Walk members backward, so each crime is used once.
for (let members = n; members >= g; members--) {
for (let prof = 0; prof <= minProfit; prof++) {
const newProf = Math.min(prof + p, minProfit);
dp[members][newProf] = (dp[members][newProf] + dp[members - g][prof]) % MOD;
}
}
}
let total = 0;
for (let members = 0; members <= n; members++) {
total = (total + dp[members][minProfit]) % MOD;
}
return total;
};Time Complexity:
minProfit.The profit cap is the trick that makes this Hard problem tractable. Without it, the profit dimension would grow with the sum of all profits instead of stopping at minProfit. Everything at or above the threshold lands in the same column, so the final answer is just the sum of that column. The backward member loop keeps each crime at one use, and the modulo keeps the counts from overflowing in languages with fixed-width integers.
These six problems cover the full knapsack family. Partition Equal Subset Sum teaches the subset sum reduction, Coin Change and Coin Change II cover both unbounded directions, Target Sum shows how to spot the pattern inside a disguise, and Ones and Zeroes plus Profitable Schemes stretch the table to two constraints. By the end you should be able to name the variant within a minute of reading a problem, and know whether it is 0/1 or unbounded, maximize or count, and one budget or two.