# 0/1 Knapsack and Subset Sum — Take It or Leave It DP

Source: https://skills101.in/learn/dsa/dsa-knapsack-subset-sum — Skills101 free tutorial (Data Structures & Algorithms). Updated 2026-11-21.

You are packing a bag for a college trek. The bag holds at most 7 kg. Each item has a **weight** and a **value** (how useful it is), and you can take each item **at most once**. Which items give the largest total value without going over 7 kg? This is the **0/1 knapsack** problem: for each item the choice is 0 (leave it) or 1 (take it). The same "take it or leave it" choice is behind subset sum, equal partition, target sum and many budget problems in placement tests.

## 1. Why greedy fails

A natural idea is to sort items by **value per kg** and take the best ones first. Try it on these four items with capacity 7:

| Item | Weight | Value | Value per kg |
|---|---|---|---|
| A | 1 | 1 | 1.00 |
| B | 3 | 4 | 1.33 |
| C | 4 | 5 | 1.25 |
| D | 5 | 7 | 1.40 |

Greedy takes D first (best ratio), leaving 2 kg. B and C no longer fit, so it adds A: total value **8**. But B + C weighs exactly 7 and is worth **9**. Taking one "good" item blocked a better pair. Because items cannot be cut into pieces, we must compare whole combinations, and DP does that without trying all 2ⁿ subsets.

(If items **can** be cut, like rice or sugar sold by weight, the problem is called **fractional knapsack** and greedy by ratio is correct. Do not mix the two up.)

## 2. The 2D table

- **State:** `dp[i][c]` = best value using only the first `i` items with capacity `c`.
- **Recurrence:** for item `i` (weight `w`, value `v`) there are two choices:
  - skip it: `dp[i − 1][c]`;
  - take it (only if `w ≤ c`): `v + dp[i − 1][c − w]`.
  - `dp[i][c]` is the larger of the two.
- **Base:** `dp[0][c] = 0` — with no items the value is 0.
- **Answer:** `dp[n][W]`, the bottom-right cell.

![0/1 knapsack table for items (w1 v1), (w3 v4), (w4 v5), (w5 v7) and capacity 0 to 7; each row adds one item, and the bottom-right cell is 9](https://skills101.in/learn-img/dsa/knapsack-table.svg)

Read the table row by row. Each new row asks only "is this item worth taking at this capacity?", using the row above. To find **which** items were taken, walk up from the bottom-right: if `dp[i][c]` differs from `dp[i − 1][c]`, item `i` was taken, so subtract its weight and continue.

```python
def knapsack(wt, val, W):
    n = len(wt)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        w, v = wt[i - 1], val[i - 1]
        for c in range(W + 1):
            dp[i][c] = dp[i - 1][c]                      # skip item i
            if w <= c:
                dp[i][c] = max(dp[i][c], v + dp[i - 1][c - w])   # take it
    taken, c = [], W
    for i in range(n, 0, -1):                            # walk back up
        if dp[i][c] != dp[i - 1][c]:
            taken.append(i - 1)
            c -= wt[i - 1]
    return dp[n][W], sorted(taken)

print(knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7))
print(knapsack([10, 20, 30], [60, 100, 120], 50))
```

```text
(9, [1, 2])
(220, [1, 2])
```

Items 1 and 2 (0-based) are B and C. Time and memory are **O(n · W)**.

## 3. One array instead of a table

Row `i` uses only row `i − 1`, so one array is enough — **if you loop the capacity from high to low**:

```python
def knapsack_1d(wt, val, W):
    dp = [0] * (W + 1)
    for w, v in zip(wt, val):
        for c in range(W, w - 1, -1):       # high to low!
            dp[c] = max(dp[c], v + dp[c - w])
    return dp[W]

def wrong_direction(wt, val, W):
    dp = [0] * (W + 1)
    for w, v in zip(wt, val):
        for c in range(w, W + 1):           # low to high
            dp[c] = max(dp[c], v + dp[c - w])
    return dp[W]

print(knapsack_1d([1, 3, 4, 5], [1, 4, 5, 7], 7))
print(wrong_direction([1, 3, 4, 5], [1, 4, 5, 7], 7))
print(knapsack_1d([3], [10], 9), wrong_direction([3], [10], 9))
```

```text
9
9
10 30
```

**Why the direction matters.** When we update `dp[c]`, the value `dp[c − w]` must still be the **old** one (from the row above, "before this item"). Going high to low, `dp[c − w]` has a smaller index and has not been touched yet in this round. Going low to high, `dp[c − w]` was **already** updated with this item, so the item gets used again. The last line shows it clearly: one item of weight 3 and value 10, capacity 9. The correct answer is 10, but the low-to-high loop takes it three times and returns 30.

## 4. Unbounded knapsack

Sometimes each item can be used **any number of times** (a shop with unlimited stock, or coins). Then the "wrong" direction above is exactly right: loop the capacity **low to high** so an item can be reused in the same round. This is the same loop as coin change in the 1D DP lesson.

| Version | Each item | 1D capacity loop |
|---|---|---|
| 0/1 knapsack | at most once | high → low |
| Unbounded knapsack | any number of times | low → high |

## 5. Subset sum and equal partition

**Subset sum:** given numbers and a `target`, can some of them (each used at most once) add up to exactly `target`? It is a knapsack where the "value" is just yes/no.

- **State:** `can[t]` = True if some subset seen so far sums to `t`.
- **Update for each number x:** `can[t] = can[t] or can[t − x]`, with `t` going from high to low (each number used once).
- **Base:** `can[0] = True` (the empty subset).

![Subset sum table for 2, 3, 7, 8 and target 11: each row shows which sums 0 to 11 are reachable after adding one more number, and 11 becomes reachable after 8](https://skills101.in/learn-img/dsa/subset-sum.svg)

**Equal partition:** can the numbers be split into two groups with the same sum? If the total is odd, no. Otherwise ask subset sum for `total / 2` — if one group reaches half, the rest is the other half.

```java
public class Main {
    static boolean subsetSum(int[] nums, int target) {
        boolean[] can = new boolean[target + 1];
        can[0] = true;
        for (int x : nums)
            for (int t = target; t >= x; t--)     // high to low: use x once
                if (can[t - x]) can[t] = true;
        return can[target];
    }

    static boolean canPartition(int[] nums) {
        int total = 0;
        for (int x : nums) total += x;
        return total % 2 == 0 && subsetSum(nums, total / 2);
    }

    public static void main(String[] args) {
        System.out.println(subsetSum(new int[]{2, 3, 7, 8}, 11));
        System.out.println(subsetSum(new int[]{2, 4, 6}, 5));
        System.out.println(canPartition(new int[]{1, 5, 11, 5}));
        System.out.println(canPartition(new int[]{1, 2, 3, 5}));
    }
}
```

```text
true
false
true
false
```

`{1, 5, 11, 5}` splits into `{11}` and `{1, 5, 5}`. `{1, 2, 3, 5}` has total 11, which is odd, so it cannot be split.

To **count** the subsets instead of checking one exists, change `or` to `+` and start with `count[0] = 1`.

```python
def count_subsets(nums, target):
    count = [1] + [0] * target
    for x in nums:
        for t in range(target, x - 1, -1):
            count[t] += count[t - x]
    return count[target]

print(count_subsets([1, 2, 3, 4, 5], 5))
print(count_subsets([2, 3, 7, 8], 11))
```

```text
3
1
```

Target 5 from 1..5 has three subsets: {5}, {1, 4} and {2, 3}.

## 6. How fast is it?

Knapsack runs in **O(n · W)**, where `W` is the capacity **number**, not the input size. With 100 items and W = 1,000 that is only 100,000 steps. With W = 10⁹ the table cannot even be stored. Such an algorithm is called **pseudo-polynomial**: fast when the numbers are small, slow when they are huge. When a problem has a small `n` (about 20) but huge weights, try all subsets with bitmasks instead.

## Common mistakes

- Using greedy by value per kg for 0/1 knapsack (it is correct only for the fractional version).
- Looping the capacity low to high in the 1D version of 0/1 knapsack, which lets an item be taken many times.
- Forgetting `can[0] = True` (or `count[0] = 1`); then nothing is ever reachable.
- In equal partition, not checking for an odd total first.
- Trying to rebuild the chosen items from the 1D array — you need the full 2D table for that.

## Quick recap

- 0/1 knapsack: `dp[i][c] = max(skip, v + dp[i − 1][c − w])`; answer at the bottom-right.
- Walk back from the corner to find the chosen items.
- 1D version: loop capacity high → low for 0/1, low → high for unbounded.
- Subset sum: `can[t] |= can[t − x]`; equal partition = subset sum to half the total.
- Time O(n · W), pseudo-polynomial; memory O(W) with one array.


Practice quiz and free certificate: https://skills101.in/learn/dsa/dsa-knapsack-subset-sum