Section Recap

You now know four major knapsack variations:

$1.$ Boolean/Subset Sum: $dp[s]$ = can we reach sum $s$? Used in partition and target sum problems.

$2.$ Counting: $dp[s]$ = how many ways? Watch loop order for combinations vs permutations.

$3.$ Bounded: Binary decomposition converts $k$ copies to $\log(k)$ items.

$4.$ Multi-dimensional: Add dimensions to the DP array for each constraint. Combined with 0/1 and unbounded knapsack from the previous section, you now have the full toolkit. Practice identifying which variation applies. That recognition skill is what separates fast problem-solvers from slow ones.