Knapsack DP Variants: 0/1, Unbounded, Fractional, Subset Sum & Target Sum

The knapsack family is the single most important DP family for interviews. Nearly every DP problem you encounter can be mapped back to one of these variants. This post covers all six, with full code and complexity analysis.

1. The 0/1 Knapsack

Problem: Given n items, each with a weight w[i] and value v[i], and a knapsack of capacity W, find the maximum total value you can carry. Each item can be used at most once.

The Recurrence

For each item i, you have two choices:

• Skip it: dp[i][w] = dp[i-1][w]
• Take it (if it fits): dp[i][w] = dp[i-1][w - w[i]] + v[i]

Take the max of both.

Full 2D Solution

def knapsack_01(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(W + 1):
            dp[i][w] = dp[i - 1][w]  # skip item i
            if weights[i - 1] <= w:
                dp[i][w] = max(
                    dp[i][w],
                    dp[i - 1][w - weights[i - 1]] + values[i - 1]
                )

    return dp[n][W]

Time: O(n * W) | Space: O(n * W)

Space-Optimised 1D Solution

Since each row only depends on the previous row, we can use a single array. The trick is to iterate weights right to left so we do not overwrite values we still need.

def knapsack_01_optimised(weights, values, W):
    n = len(weights)
    dp = [0] * (W + 1)

    for i in range(n):
        for w in range(W, weights[i] - 1, -1):  # right to left
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

    return dp[W]

Time: O(n * W) | Space: O(W)

Why Right to Left?

If we go left to right, dp[w - weights[i]] might already include item i from this same iteration, effectively allowing unlimited copies. That is the unbounded variant (next section). Right-to-left ensures each item is used at most once.

Reconstructing the Solution

def knapsack_01_with_items(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(W + 1):
            dp[i][w] = dp[i - 1][w]
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])

    # Backtrack to find which items were picked
    items = []
    w = W
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i - 1][w]:
            items.append(i - 1)
            w -= weights[i - 1]

    return dp[n][W], items[::-1]

---

2. Unbounded Knapsack

Problem: Same as 0/1 knapsack, but each item can be used unlimited times.

The Key Difference

In 0/1 knapsack we look at dp[i-1][w - w[i]] (previous row). In unbounded, we look at dp[i][w - w[i]] (same row), because we can take item i again.

def knapsack_unbounded(weights, values, W):
    dp = [0] * (W + 1)

    for i in range(len(weights)):
        for w in range(weights[i], W + 1):  # LEFT to RIGHT
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

    return dp[W]

Time: O(n * W) | Space: O(W)

Notice: the only code difference from the 1D 0/1 knapsack is the loop direction. Left-to-right allows reusing the same item.

Classic Applications

Problem	Mapping
Coin Change (min coins)	Unbounded knapsack, minimise count
Coin Change 2 (count ways)	Unbounded knapsack, count combinations
Rod Cutting	Unbounded knapsack on rod lengths
Integer Break	Unbounded knapsack on factors

Coin Change Example

def coin_change(coins, amount):
    """Minimum coins to make amount."""
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for coin in coins:
        for a in range(coin, amount + 1):
            dp[a] = min(dp[a], dp[a - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

---

3. Fractional Knapsack

Problem: You can take fractions of items. This is the only variant that is greedy, not DP.

Why Greedy Works

When you can break items, the optimal strategy is always to take the item with the highest value-to-weight ratio first. There is no overlapping subproblem structure.

def fractional_knapsack(weights, values, W):
    items = sorted(
        zip(values, weights),
        key=lambda x: x[0] / x[1],
        reverse=True
    )

    total_value = 0
    remaining = W

    for v, w in items:
        if remaining >= w:
            total_value += v
            remaining -= w
        else:
            total_value += v * (remaining / w)
            break

    return total_value

Time: O(n log n) for sorting | Space: O(n)

Comparison Table

Variant	Items	Approach	Time
0/1 Knapsack	Use once	DP	O(nW)
Unbounded	Unlimited	DP	O(nW)
Fractional	Breakable	Greedy	O(n log n)

---

4. Subset Sum

Problem: Given an array of positive integers and a target S, determine if any subset sums to S.

This is a boolean 0/1 knapsack where the “value” is irrelevant and the “weight” equals the number itself.

def subset_sum(nums, target):
    dp = [False] * (target + 1)
    dp[0] = True

    for num in nums:
        for s in range(target, num - 1, -1):  # right to left (0/1)
            dp[s] = dp[s] or dp[s - num]

    return dp[target]

Time: O(n * target) | Space: O(target)

Counting Subsets

To count the number of subsets that sum to S:

def count_subsets(nums, target):
    dp = [0] * (target + 1)
    dp[0] = 1

    for num in nums:
        for s in range(target, num - 1, -1):
            dp[s] += dp[s - num]

    return dp[target]

---

5. Partition Equal Subset Sum

Problem: Can the array be partitioned into two subsets with equal sum? (LeetCode 416)

Reduction to Subset Sum

If the total sum is odd, the answer is immediately False. Otherwise, find if a subset sums to total // 2.

def can_partition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False

    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True

    for num in nums:
        for s in range(target, num - 1, -1):
            dp[s] = dp[s] or dp[s - num]

    return dp[target]

Time: O(n * sum/2) | Space: O(sum/2)

Optimisation with Bitset

Python integers have arbitrary precision, so we can use bit shifts for a constant-factor speedup:

def can_partition_bitset(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False

    target = total // 2
    bits = 1  # bit 0 is set (sum 0 is reachable)

    for num in nums:
        bits |= bits << num

    return bool(bits & (1 << target))

This runs the same O(n * sum) work but with hardware-level bit parallelism.

---

6. Target Sum

Problem: Given an array nums and a target, assign + or - to each element to reach the target. Count the number of ways. (LeetCode 494)

The Math Reduction

Let P = sum of elements assigned +, N = sum of elements assigned -.

• P + N = total
• P - N = target

Adding: 2P = total + target, so P = (total + target) / 2.

The problem reduces to: count subsets summing to P.

def find_target_sum_ways(nums, target):
    total = sum(nums)

    # P must be a non-negative integer
    if (total + target) % 2 != 0 or total + target < 0:
        return 0

    subset_target = (total + target) // 2
    dp = [0] * (subset_target + 1)
    dp[0] = 1

    for num in nums:
        for s in range(subset_target, num - 1, -1):
            dp[s] += dp[s - num]

    return dp[subset_target]

Time: O(n * P) where P = (total + target) / 2 | Space: O(P)

Edge Case: Zeros in the Array

Each zero can be assigned either + or - without affecting the sum, so each zero doubles the number of valid assignments. The DP handles this naturally since dp[s] += dp[s - 0] doubles every entry.

---

Variant Comparison

Problem	Core Idea	Loop Direction	What dp[j] Stores
0/1 Knapsack	Pick or skip	Right to left	Max value
Unbounded	Reuse allowed	Left to right	Max value
Subset Sum	Exists a subset?	Right to left	Boolean
Count Subsets	How many subsets?	Right to left	Count
Partition	Sum to total/2?	Right to left	Boolean
Target Sum	Count +/- combos	Right to left	Count

---

Common Mistakes

1. Wrong loop direction: Left-to-right in 0/1 knapsack allows reuse, giving wrong answers.
2. Off-by-one in range: The inner loop should go down to num (inclusive), not num + 1.
3. Forgetting the odd-sum check in partition equal subset.
4. Not handling negative numbers in target sum. The math reduction avoids negative indices.
5. Initialising dp[0] wrong: For counting, dp[0] = 1. For min-cost, dp[0] = 0 and rest = infinity.

---

Big-O Summary

Variant	Time	Space (optimised)
0/1 Knapsack	O(n * W)	O(W)
Unbounded Knapsack	O(n * W)	O(W)
Fractional Knapsack	O(n log n)	O(n)
Subset Sum	O(n * S)	O(S)
Partition Equal	O(n * S/2)	O(S/2)
Target Sum	O(n * P)	O(P)

---

Practice Problems

Problem	Platform	Difficulty	Variant
0/1 Knapsack	GFG	Medium	Classic
Partition Equal Subset Sum	LeetCode 416	Medium	Subset Sum
Target Sum	LeetCode 494	Medium	Count Subsets
Coin Change	LeetCode 322	Medium	Unbounded
Coin Change 2	LeetCode 518	Medium	Unbounded Count
Last Stone Weight II	LeetCode 1049	Medium	Partition
Ones and Zeroes	LeetCode 474	Medium	2D Knapsack
Profitable Schemes	LeetCode 879	Hard	2D Knapsack

---

Key Takeaway

Every knapsack variant shares the same skeleton: iterate over items, iterate over capacities, and decide to include or exclude. The differences are:

• Loop direction (right-to-left for 0/1, left-to-right for unbounded)
• What you track (max value, boolean, count)
• What you optimise (value, existence, count of ways)

Master the 0/1 template and you can derive every other variant on the spot.