Knapsack DP

Opening scenario

Problem references use LC for LeetCode.

Given an array nums of positive integers, decide whether it can be split into two subsets with equal sum (LC 416, Partition Equal Subset Sum). Then the interviewer varies it. Count the ways: return how many subsets hit the target sum, not just yes or no. Add a second budget: the chosen subset must now stay under two limits at once. Allow reusing elements: a number may be picked as many times as you like. All of these are one family.

For equal partition, every item belongs to one of the two subsets and can be used only once. Equal-valued items at different indices are distinct items. Start by deciding which earlier choices affect whether the remaining target can be reached.

Question progression

Q1 — Why is "pick the biggest items first" wrong, and what is the real state?

Question: For LC 416 you target sum S = total / 2. A greedy "take the largest item that still fits" fails on…