Intermediate

Knapsack Patterns

The knapsack family is the most frequently tested DP pattern in coding interviews. Once you understand the 0/1 knapsack template, you can solve dozens of variations by recognizing the underlying structure. Five problems, each building on the previous one.

Problem 1: 0/1 Knapsack

Problem: Given n items with weights and values, and a knapsack with capacity W, find the maximum value you can carry. Each item can be used at most once.

State: dp[i][w] = maximum value using items 0..i-1 with capacity w.

Recurrence: dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i]) if weight[i] <= w, else dp[i][w] = dp[i-1][w].

# Brute force: O(2^n) - try including/excluding each item
def knapsack_brute(weights, values, capacity, i=None):
    if i is None: i = len(weights) - 1
    if i < 0 or capacity <= 0:
        return 0
    # Option 1: skip item i
    skip = knapsack_brute(weights, values, capacity, i - 1)
    # Option 2: take item i (if it fits)
    take = 0
    if weights[i] <= capacity:
        take = values[i] + knapsack_brute(weights, values, capacity - weights[i], i - 1)
    return max(skip, take)

# Memoization: O(n * W) time, O(n * W) space
def knapsack_memo(weights, values, capacity):
    n = len(weights)
    memo = {}
    def dp(i, w):
        if i < 0 or w <= 0:
            return 0
        if (i, w) in memo:
            return memo[(i, w)]
        skip = dp(i - 1, w)
        take = 0
        if weights[i] <= w:
            take = values[i] + dp(i - 1, w - weights[i])
        memo[(i, w)] = max(skip, take)
        return memo[(i, w)]
    return dp(n - 1, capacity)

# Tabulation: O(n * W) time, O(W) space (1D optimization)
def knapsack_tab(weights, values, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)
    for i in range(n):
        # Traverse RIGHT to LEFT to avoid using item i twice
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[capacity]

# Test:
weights = [2, 3, 4, 5]
values  = [3, 4, 5, 6]
# knapsack_tab(weights, values, 8) = 10 (items with weight 3,5 -> value 4+6)

Problem 2: Unbounded Knapsack

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

Key difference: Iterate capacity LEFT to RIGHT so items can be reused.

# Brute force: O(W^n) time
def unbounded_brute(weights, values, capacity, i=None):
    if i is None: i = len(weights) - 1
    if i < 0 or capacity <= 0:
        return 0
    skip = unbounded_brute(weights, values, capacity, i - 1)
    take = 0
    if weights[i] <= capacity:
        # Note: i stays the same (can reuse item i)
        take = values[i] + unbounded_brute(weights, values, capacity - weights[i], i)
    return max(skip, take)

# Tabulation: O(n * W) time, O(W) space
def unbounded_tab(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for i in range(len(weights)):
        # LEFT to RIGHT: allows reusing item i
        for w in range(weights[i], capacity + 1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[capacity]

# Test:
weights = [2, 3, 4, 5]
values  = [3, 4, 5, 6]
# unbounded_tab(weights, values, 8) = 12 (four items of weight 2, value 3 each)

Problem 3: Subset Sum

Problem: Given a set of non-negative integers and a target sum, determine if there is a subset whose sum equals the target.

Connection to knapsack: This is 0/1 knapsack where weight = value = the number itself, and we check if we can exactly fill capacity = target.

# Brute force: O(2^n)
def subset_sum_brute(nums, target, i=None):
    if i is None: i = len(nums) - 1
    if target == 0:
        return True
    if i < 0 or target < 0:
        return False
    # Include or exclude nums[i]
    return (subset_sum_brute(nums, target - nums[i], i - 1) or
            subset_sum_brute(nums, target, i - 1))

# Tabulation: O(n * target) time, O(target) space
def subset_sum_tab(nums, target):
    dp = [False] * (target + 1)
    dp[0] = True  # Empty subset sums to 0
    for num in nums:
        # Right to left (0/1: each number used once)
        for s in range(target, num - 1, -1):
            if dp[s - num]:
                dp[s] = True
    return dp[target]

# Test: subset_sum_tab([3, 34, 4, 12, 5, 2], 9) = True (4 + 5)
# Test: subset_sum_tab([3, 34, 4, 12, 5, 2], 30) = False

Problem 4: Partition Equal Subset Sum

Problem: Given a non-empty array of positive integers, determine if it can be partitioned into two subsets with equal sum.

Reduction: If total sum is odd, return False. Otherwise, this is subset sum with target = total_sum / 2.

# Direct reduction to subset sum
def can_partition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False  # Odd sum cannot be split equally
    target = total // 2

    # Subset sum with target = total/2
    dp = [False] * (target + 1)
    dp[0] = True
    for num in nums:
        for s in range(target, num - 1, -1):
            if dp[s - num]:
                dp[s] = True
    return dp[target]

# Optimized with bitset (Python int as unlimited-length bitset)
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 achievable
    for num in nums:
        bits |= (bits << num)
    return bool(bits & (1 << target))

# Test: can_partition([1, 5, 11, 5]) = True ([1,5,5] and [11])
# Test: can_partition([1, 2, 3, 5]) = False

Problem 5: Target Sum

Problem: Given an array of integers and a target, assign + or - to each integer. Find the number of ways to achieve the target sum.

Reduction: Let P = subset with + signs, N = subset with - signs. Then P - N = target and P + N = total. So P = (target + total) / 2. This reduces to counting subsets with sum P.

# Brute force: O(2^n) - try +/- for each number
def target_sum_brute(nums, target, i=0, curr=0):
    if i == len(nums):
        return 1 if curr == target else 0
    return (target_sum_brute(nums, target, i + 1, curr + nums[i]) +
            target_sum_brute(nums, target, i + 1, curr - nums[i]))

# Memoization: O(n * total_sum) time
def target_sum_memo(nums, target):
    memo = {}
    def dp(i, curr):
        if i == len(nums):
            return 1 if curr == target else 0
        if (i, curr) in memo:
            return memo[(i, curr)]
        memo[(i, curr)] = dp(i + 1, curr + nums[i]) + dp(i + 1, curr - nums[i])
        return memo[(i, curr)]
    return dp(0, 0)

# Tabulation via subset sum reduction: O(n * P) time, O(P) space
def target_sum_tab(nums, target):
    total = sum(nums)
    # P = (target + total) / 2 must be a non-negative integer
    if (target + total) % 2 != 0 or abs(target) > total:
        return 0
    P = (target + total) // 2

    # Count subsets that sum to P
    dp = [0] * (P + 1)
    dp[0] = 1
    for num in nums:
        for s in range(P, num - 1, -1):
            dp[s] += dp[s - num]
    return dp[P]

# Test: target_sum_tab([1,1,1,1,1], 3) = 5
# Five ways: -1+1+1+1+1, +1-1+1+1+1, +1+1-1+1+1, +1+1+1-1+1, +1+1+1+1-1

Complexity Summary

Problem	Brute Force	DP Time	Optimized Space
0/1 Knapsack	O(2^n)	O(n × W)	O(W)
Unbounded Knapsack	O(W^n)	O(n × W)	O(W)
Subset Sum	O(2^n)	O(n × target)	O(target)
Partition Equal Subset	O(2^n)	O(n × sum/2)	O(sum/2)
Target Sum	O(2^n)	O(n × P)	O(P)

Key Takeaways

• The 0/1 knapsack template is the foundation: include or exclude each item, track remaining capacity.
• Right-to-left iteration in 1D tabulation ensures each item is used at most once (0/1). Left-to-right allows reuse (unbounded).
• Many problems that do not look like knapsack can be reduced to it: subset sum, partition, and target sum are all disguised knapsack problems.
• The subset sum reduction (P = (target + total) / 2) is a powerful technique that converts a counting problem into a standard knapsack.
• The bitset optimization for partition equal subset is a practical technique that interviewers appreciate seeing.