# Dynamic Programming Knapsack Patterns: 0/1, Unbounded, Subset Sum

Source: https://www.techinterview.org/post/3233461350/dynamic-programming-knapsack-patterns/
Updated: 2026-07-05 · techinterview.org

Knapsack problems are the most important dynamic programming pattern class. Mastering 0/1 knapsack, unbounded knapsack, and their variants (subset sum, coin change, partition equal subset) unlocks a wide range of interview problems at top tech companies.

## 0/1 Knapsack: The Template


```
Problem: given items with weights and values, and capacity W,
         maximize total value without exceeding capacity.
         Each item can be used at most once (0/1).

def knapsack_01(weights: list, values: list, W: int) -> int:
    n = len(weights)
    # dp[i][w] = max value using first i items with capacity w
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        w_i, v_i = weights[i-1], values[i-1]
        for w in range(W + 1):
            # Option 1: skip item i
            dp[i][w] = dp[i-1][w]
            # Option 2: take item i (if it fits)
            if w >= w_i:
                dp[i][w] = max(dp[i][w], dp[i-1][w - w_i] + v_i)
    return dp[n][W]

# Space optimization to O(W): iterate weights in reverse
def knapsack_01_optimized(weights, values, W):
    dp = [0] * (W + 1)
    for w_i, v_i in zip(weights, values):
        for w in range(W, w_i - 1, -1):  # ← REVERSE: prevents using same item twice
            dp[w] = max(dp[w], dp[w - w_i] + v_i)
    return dp[W]

# Time: O(n × W), Space: O(W)
```


## Pattern: Subset Sum


```
def canPartition(nums: list[int]) -> bool:
    """LC 416: partition array into two equal-sum subsets"""
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    # dp[w] = can we form sum w using some subset?
    dp = [False] * (target + 1)
    dp[0] = True  # empty subset sums to 0
    for num in nums:
        for w in range(target, num - 1, -1):  # reverse to avoid reuse
            dp[w] = dp[w] or dp[w - num]
    return dp[target]

# Generalization: find subset summing to target
def subsetSum(nums: list[int], target: int) -> bool:
    dp = [False] * (target + 1)
    dp[0] = True
    for num in nums:
        for w in range(target, num - 1, -1):
            if dp[w - num]:
                dp[w] = True
    return dp[target]
```


## Pattern: Unbounded Knapsack (items reusable)


```
def knapsack_unbounded(weights, values, W):
    """Each item can be used unlimited times"""
    dp = [0] * (W + 1)
    for w_i, v_i in zip(weights, values):
        for w in range(w_i, W + 1):  # ← FORWARD: allows reusing same item
            dp[w] = max(dp[w], dp[w - w_i] + v_i)
    return dp[W]

# Key insight: reverse loop = 0/1 (each item once)
#              forward loop = unbounded (item reusable)
```


## Pattern: Coin Change (Minimum Coins)


```
def coinChange(coins: list[int], amount: int) -> int:
    """LC 322: fewest coins to make amount — unbounded knapsack variant"""
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for coin in coins:
        for amt in range(coin, amount + 1):  # forward: coins reusable
            if dp[amt - coin] != float('inf'):
                dp[amt] = min(dp[amt], dp[amt - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

def coinChangeWays(coins: list[int], amount: int) -> int:
    """LC 518: number of combinations to make amount"""
    dp = [0] * (amount + 1)
    dp[0] = 1  # one way to make 0: use no coins
    for coin in coins:
        for amt in range(coin, amount + 1):
            dp[amt] += dp[amt - coin]
    return dp[amount]

# NOTE: outer loop is coins, inner is amount → each combination counted once
# If outer loop were amount and inner coins → permutations (order matters)
```


## Pattern: Target Sum (LC 494)


```
def findTargetSumWays(nums: list[int], target: int) -> int:
    """Assign + or - to each num to reach target"""
    # Let P = set of positives, N = set of negatives
    # P - N = target, P + N = total
    # → 2P = target + total → P = (target + total) / 2
    # Count subsets summing to (target + total) // 2
    total = sum(nums)
    if (total + target) % 2 != 0 or abs(target) > total:
        return 0
    subset_target = (total + target) // 2
    dp = [0] * (subset_target + 1)
    dp[0] = 1
    for num in nums:
        for w in range(subset_target, num - 1, -1):
            dp[w] += dp[w - num]
    return dp[subset_target]
```


## Pattern: Last Stone Weight II (LC 1049)


```
def lastStoneWeightII(stones: list[int]) -> int:
    """Minimize |sum(group1) - sum(group2)| = minimize 2×sum(group1) - total"""
    # Equivalent to: find subset sum closest to total//2
    total = sum(stones)
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    for s in stones:
        for w in range(target, s - 1, -1):
            dp[w] = dp[w] or dp[w - s]
    # Find largest achievable sum ≤ target
    for s in range(target, -1, -1):
        if dp[s]:
            return total - 2 * s
```


## Pattern: 2D Knapsack (Ones and Zeroes, LC 474)


```
def findMaxForm(strs: list[str], m: int, n: int) -> int:
    """Largest subset with at most m zeros and n ones — 2D knapsack"""
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for s in strs:
        zeros = s.count('0')
        ones = len(s) - zeros
        # Reverse both dimensions (0/1: each string used once)
        for i in range(m, zeros - 1, -1):
            for j in range(n, ones - 1, -1):
                dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)
    return dp[m][n]
```


## Pattern: Bounded Knapsack (each item limited count)


```
def knapsack_bounded(weights, values, counts, W):
    """Each item i can be used at most counts[i] times"""
    dp = [0] * (W + 1)
    for w_i, v_i, c_i in zip(weights, values, counts):
        # Binary grouping: represent count as 1 + 2 + 4 + ... + remainder
        # Reduces to 0/1 knapsack with O(sum(log c_i)) groups
        groups = []
        k = 1
        remaining = c_i
        while k <= remaining:
            groups.append((k * w_i, k * v_i))
            remaining -= k
            k *= 2
        if remaining > 0:
            groups.append((remaining * w_i, remaining * v_i))
        # Now apply 0/1 knapsack for each group
        for gw, gv in groups:
            for w in range(W, gw - 1, -1):
                dp[w] = max(dp[w], dp[w - gw] + gv)
    return dp[W]
```


## Knapsack Variant Recognition

| Problem Signal | Variant | Loop Direction |
| --- | --- | --- |
| "each item used at most once" | 0/1 Knapsack | Reverse inner loop |
| "unlimited supply of each item" | Unbounded | Forward inner loop |
| "each item limited to k times" | Bounded | Binary grouping → 0/1 |
| "can we achieve exactly X" | Subset Sum (bool) | Reverse, OR updates |
| "how many ways to make X" | Count combinations | Forward (coins outer) |
| "minimize coins/items to make X" | Coin Change | Forward, min updates |

## Key Interview Tips

- **The one rule to remember**: Reverse inner loop for 0/1 (prevents reusing the item in the same pass). Forward inner loop for unbounded (enables reusing the item). This single distinction separates all knapsack variants.

- **Outer loop order matters for counting**: Coin change COMBINATIONS (outer = items, inner = amounts) counts each combination once. Coin change PERMUTATIONS (outer = amounts, inner = items) counts each ordering separately.

- **Subset sum as boolean knapsack**: Replace max() with OR, and value with 1. The DP recurrence is identical — this mental mapping unlocks LC 416, 494, 1049, and similar problems.

- **Space optimization**: The 2D DP table always collapses to a 1D array because dp[i][w] only depends on dp[i-1][w] and dp[i-1][w-w_i]. Start by writing the 2D solution for clarity, then optimize to 1D.

- [Coinbase Interview Guide](https://techinterview.org/coinbase-interview-guide/)

- [LinkedIn Interview Guide](https://techinterview.org/linkedin-interview-guide/)

- [Atlassian Interview Guide](https://techinterview.org/atlassian-interview-guide/)

- [Uber Interview Guide](https://techinterview.org/uber-interview-guide/)

- [Apple Interview Guide](https://techinterview.org/apple-interview-guide/)

## Companies That Ask This

- [Meta Interview Guide](https://techinterview.org/meta-interview-guide/)