0/1 Knapsack & Subsets

0/1 Knapsack & Subsets

The knapsack problem: you have items, each with a weight and a value, and a bag with a capacity. Choose items to maximize total value without exceeding the capacity. In the 0/1 version each item is either taken once or not at all. You can't take fractions or repeats.

It matters far beyond bags. The same structure, "choose a subset of items subject to a budget, and optimize or count", underlies partitioning an array into equal halves, counting ways to reach a target sum, budget allocation and resource scheduling. Recognising "this is knapsack in disguise" is the real interview skill.

Why greedy fails

Taking the best value-per-weight item first seems natural. With capacity 50:

Greedy takes A then B: weight 30, value 160. C doesn't fit in the remaining 20. The optimum is B + C = 220. Greedy works for the fractional knapsack (you can take part of C), but not for 0/1, which needs dynamic programming.

The recurrence

Define dp[i][w] = the best value using only the first i items with capacity w. For item i, there are exactly two choices:

skip item i:   dp[i-1][w]
take item i:   dp[i-1][w - weight_i] + value_i        (only if weight_i <= w)

dp[i][w] = max(skip, take)          base case: dp[0][w] = 0 (no items → no value)

"Take" looks at row i-1, the state before item i was available. That's exactly what enforces "each item at most once".

public int knapsack(int[] weight, int[] value, int capacity) {
    int n = weight.length;
    int[][] dp = new int[n + 1][capacity + 1];
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= capacity; w++) {
            dp[i][w] = dp[i - 1][w];                                             // skip
            if (weight[i - 1] <= w)
                dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - weight[i - 1]] + value[i - 1]);   // take
        }
    }
    return dp[n][capacity];
}

O(n × W) time and space, where W is the capacity. Note that this is pseudo-polynomial: it's fast when W is small, but if capacities are in the billions the table is impossible. Knapsack is NP-hard in general.

Which items were chosen?

Walk the table backwards: if dp[i][w] != dp[i-1][w], item i was taken, so subtract its weight and continue from row i-1.

Space optimization: one row, iterated backwards

Each row only reads the previous row, so a single array suffices. The iteration order is the crucial detail:

int[] dp = new int[capacity + 1];
for (int i = 0; i < n; i++) {
    for (int w = capacity; w >= weight[i]; w--) {        // BACKWARDS
        dp[w] = Math.max(dp[w], dp[w - weight[i]] + value[i]);
    }
}
return dp[capacity];

Why backwards? dp[w − weight] must still hold the value from before item i was considered. Going from high w to low w, the smaller indexes haven't been updated yet in this round. Going forwards, dp[w − weight] may already include item i, so the item could be used twice. That accidentally solves the unbounded knapsack instead.

Knapsack in disguise

Partition Equal Subset Sum

Both halves must sum to total / 2, so the question becomes "is there a subset summing to total/2?". That's a knapsack where value doesn't matter, only reachability:

public boolean canPartition(int[] nums) {
    int total = 0;
    for (int x : nums) total += x;
    if (total % 2 != 0) return false;            // an odd total can't split evenly
    int target = total / 2;

    boolean[] reachable = new boolean[target + 1];
    reachable[0] = true;                          // the empty subset sums to 0
    for (int x : nums)
        for (int s = target; s >= x; s--)         // backwards: each number used once
            reachable[s] = reachable[s] || reachable[s - x];
    return reachable[target];
}

It's O(n × target) time and O(target) space. You can stop early once reachable[target] becomes true.

Count subsets with a given sum

Replace "reachable?" with "in how many ways?": + instead of ||.

int countSubsets(int[] nums, int target) {
    int[] ways = new int[target + 1];
    ways[0] = 1;
    for (int x : nums)
        for (int s = target; s >= x; s--)
            ways[s] += ways[s - x];
    return ways[target];
}

(With zeros in the input, each zero doubles the count. This loop handles that correctly, because ways[s] += ways[s − 0] doubles ways[s].)

Target Sum: assign + or − to every number

Let P be the numbers given + and N those given −. Then P − N = target and P + N = total. Adding the two equations gives P = (total + target) / 2. So the answer is the number of subsets summing to (total + target)/2, a direct call to countSubsets after checking that the value is a non-negative integer:

public int findTargetSumWays(int[] nums, int target) {
    int total = Arrays.stream(nums).sum();
    if (Math.abs(target) > total || (total + target) % 2 != 0) return 0;
    return countSubsets(nums, (total + target) / 2);
}

This algebraic reduction, turning signs into a subset choice, is a trick worth remembering. It's what turns an exponential search into an O(n × total) DP.

Last Stone Weight II

Smashing stones repeatedly ends up equivalent to splitting them into two groups and taking the difference. Minimizing it means finding the subset sum closest to total/2, the same reachability table, then scanning downwards from total/2 for the first reachable sum.

How to spot a knapsack problem

• You choose a subset of items (each used once, or unlimited for the unbounded variant),
• subject to a budget or target (weight, sum, count),
• and you maximize, minimize, count ways, or check feasibility.

Then the state is almost always dp[budget] (plus the item index in the 2-D form), and the transition is "skip it, or take it".

Follow-up questions this topic invites — and their answers

Q: Why must the 1-D loop go backwards for 0/1 knapsack? A: So that dp[w − weight] still refers to the previous item's row. Going forwards would let the current item update a smaller capacity and then be counted again at a larger one, allowing multiple copies. That's exactly the unbounded knapsack.

Q: Is knapsack polynomial? A: The DP is O(n × W), which is polynomial in the numeric value of W but exponential in the number of bits needed to write W down, so it's called pseudo-polynomial. The general problem is NP-hard. For huge capacities with few items, meet-in-the-middle (split the items in half and enumerate each) can be better.

Q: How would you handle fractional items? A: Fractional knapsack is solved greedily: sort by value/weight and take items fully until the next doesn't fit, then take the fraction that fits. It's O(n log n) and provably optimal because partial items remove the all-or-nothing constraint.

Q: What if each item can be used up to k times (bounded knapsack)? A: Expand each item into copies, or better, into binary-split bundles (1, 2, 4, … copies) so that any count up to k can be formed, then run 0/1 knapsack. That's O(n × W × log k) instead of O(n × W × k).

Q: How does Partition Equal Subset Sum relate to knapsack? A: It's a 0/1 knapsack where each number's "weight" is its value, the capacity is total/2, and the question is only whether that exact capacity can be filled. Reachability replaces maximization.