LeetCode Solutions← Back to Patterns
Dynamic ProgrammingHard
Knapsack
Optimize item selection under a capacity or count constraint.
How it works
The Knapsack pattern models problems where you select a subset of items to maximize value (or minimize cost) under a constraint like weight or count. In the 0/1 Knapsack, each item can be used at most once: iterate items in the outer loop, then iterate capacity in reverse (to prevent reuse). In the Unbounded Knapsack (Coin Change), each item can be used unlimited times: iterate capacity forward. The DP state is dp[c] = best value achievable with exactly (or at most) capacity c. Key variants include: Partition Equal Subset Sum (can we split the array into two equal halves?), Target Sum (reach a target by assigning +/- signs), and Coin Change (minimum coins for amount).
Interactive Playground
Items: (w=2,v=6), (w=3,v=10), (w=4,v=12). Bag capacity = 5.
Speed
When to use
- 0/1 knapsack — include or exclude each item once
- Partition equal subset sum
- Coin change with unlimited denominations
✅Tips
10/1 Knapsack: iterate capacity from high to low to ensure each item is used at most once.
2Unbounded Knapsack (coin change): iterate capacity from low to high to allow reuse.
3For Partition Equal Subset Sum, find total sum first — if odd, return false immediately.
4Initialize dp[0] = true (or 0 cost) for existence problems; dp[amount] = Infinity for min-cost problems except dp[0] = 0.
❌Common Mistakes
!Iterating capacity forward for 0/1 Knapsack — allows items to be counted multiple times.
!Wrong initialization of dp array — dp[0] = 0 for min-cost, dp[0] = true for boolean reachability.
!Not handling the case where it's impossible to reach the target — return -1 or false when dp[target] is still Infinity/false.
!Forgetting the total sum parity check for Partition Equal Subset Sum.
💡 Key Insight:For each item, decide: include or exclude. Iterate in reverse to avoid reuse (0/1).