Knapsack Patterns - Data Structures & Algorithms

The knapsack is one of the most important DP patterns. A shocking number of interview problems are just knapsack in disguise. Once we learn this pattern, we unlock a whole family of problems.

In simple language, we have a bag with limited capacity and items to choose from. We want to pick the best combination without exceeding the limit.

0/1 Knapsack

Problem: We have n items, each with a weight and value. Our bag holds at most W weight. Find the maximum value we can carry. Each item can only be used once (take it or leave it — that’s the “0/1”).

State: dp[i][w] = max value using first i items with capacity w

Recurrence: For each item, we either skip it or take it (if it fits):

Skip: dp[i][w] = dp[i-1][w]
Take: dp[i][w] = dp[i-1][w - weight[i]] + value[i]
Pick whichever gives more value.

The Decision Tree

0/1 Knapsack: Items [(wt:1,val:6), (wt:2,val:10), (wt:3,val:12)], Capacity: 5

Item 1 (wt:1, val:6)

Skip

cap=5, val=0

Take

cap=4, val=6

Each branch continues with Item 2, then Item 3...

Overlapping subproblems appear when different paths reach the same (item, capacity) state

Best: Take items 2+3 = value 22 (weight 5)

The DP Table

DP Table — rows: items, cols: capacity 0-5

	1	2	3	4	5
no items	0	0	0	0	0
wt:1 v:6	6	6	6	6	6
wt:2 v:10	6	10	16	16	16
wt:3 v:12	6	10	16	18	22

Answer at bottom-right: max value = 22 with capacity 5

function knapsack(weights, values, capacity) {
  const n = weights.length;
  const dp = Array.from({ length: n + 1 },
    () => new Array(capacity + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= capacity; w++) {
      dp[i][w] = dp[i - 1][w];                     // skip this item
      if (weights[i - 1] <= w) {                    // can we take it?
        dp[i][w] = Math.max(dp[i][w],
          dp[i - 1][w - weights[i - 1]] + values[i - 1]); // take it
      }
    }
  }
  return dp[n][capacity];
}
// Time: O(n * capacity), Space: O(n * capacity)

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]                  # skip this item
            if weights[i - 1] <= w:                   # can we take it?
                dp[i][w] = max(dp[i][w],
                    dp[i - 1][w - weights[i - 1]] + values[i - 1])
    return dp[n][capacity]
# Time: O(n * capacity), Space: O(n * capacity)

static int knapsack(int[] weights, int[] values, int capacity) {
    int n = weights.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 (weights[i - 1] <= w) {                // can we take it?
                dp[i][w] = Math.max(dp[i][w],
                    dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            }
        }
    }
    return dp[n][capacity];
}
// Time: O(n * capacity), Space: O(n * capacity)

Space-Optimized 0/1 Knapsack

We only ever look at the previous row. So we can use a single 1D array — but we must iterate capacity backwards to avoid using an item twice.

function knapsack(weights, values, capacity) {
  const dp = new Array(capacity + 1).fill(0);
  for (let i = 0; i < weights.length; i++) {
    for (let w = capacity; w >= weights[i]; w--) {  // backwards!
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
    }
  }
  return dp[capacity];
}
// Space: O(capacity) — much better!

def knapsack(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for i in range(len(weights)):
        for w in range(capacity, weights[i] - 1, -1):  # backwards!
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[capacity]
# Space: O(capacity) — much better!

static int knapsack(int[] weights, int[] values, int capacity) {
    int[] dp = new int[capacity + 1];
    for (int i = 0; i < weights.length; i++) {
        for (int w = capacity; w >= weights[i]; w--) { // backwards!
            dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}
// Space: O(capacity) — much better!

Why backwards? Going forward would let us use the same item multiple times (since dp[w - weight] was already updated in this round). Going backwards ensures we only use each item once.

Unbounded Knapsack

Same problem but each item can be used unlimited times. The only change? We iterate capacity forwards instead of backwards.

This is actually the same idea as coin change — coins are items, denominations are weights, and we want to maximize value (or minimize count).

function unboundedKnapsack(weights, values, capacity) {
  const dp = new Array(capacity + 1).fill(0);
  for (let i = 0; i < weights.length; i++) {
    for (let w = weights[i]; w <= capacity; w++) {  // forwards = reuse!
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
    }
  }
  return dp[capacity];
}

def unbounded_knapsack(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for i in range(len(weights)):
        for w in range(weights[i], capacity + 1):     # forwards = reuse!
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[capacity]

static int unboundedKnapsack(int[] weights, int[] values, int capacity) {
    int[] dp = new int[capacity + 1];
    for (int i = 0; i < weights.length; i++) {
        for (int w = weights[i]; w <= capacity; w++) { // forwards = reuse!
            dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

Subset Sum

Problem: Given an array of positive integers and a target, can we find a subset that sums to exactly the target?

This is 0/1 knapsack where every item’s “value” equals its “weight” and we want to hit exactly the capacity.

State: dp[s] = can we make sum s?

function canSubsetSum(nums, target) {
  const dp = new Array(target + 1).fill(false);
  dp[0] = true;                          // empty subset has sum 0
  for (const num of nums) {
    for (let s = target; s >= num; s--) { // backwards = use each once
      if (dp[s - num]) dp[s] = true;
    }
  }
  return dp[target];
}

def can_subset_sum(nums, target):
    dp = [False] * (target + 1)
    dp[0] = True                          # empty subset has sum 0
    for num in nums:
        for s in range(target, num - 1, -1):  # backwards = use each once
            if dp[s - num]:
                dp[s] = True
    return dp[target]

static boolean canSubsetSum(int[] nums, int target) {
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;                          // empty subset has sum 0
    for (int num : nums) {
        for (int s = target; s >= num; s--) { // backwards = use each once
            if (dp[s - num]) dp[s] = true;
        }
    }
    return dp[target];
}

Partition Equal Subset Sum

Problem: Can we partition an array into two subsets with equal sum?

This is just subset sum in disguise. If the total sum is odd, it’s impossible. If it’s even, we just need to find a subset that sums to totalSum / 2.

function canPartition(nums) {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % 2 !== 0) return false;       // odd sum = impossible
  return canSubsetSum(nums, total / 2);    // reuse subset sum!
}

def can_partition(nums):
    total = sum(nums)
    if total % 2 != 0: return False        # odd sum = impossible
    return can_subset_sum(nums, total // 2)  # reuse subset sum!

static boolean canPartition(int[] nums) {
    int total = Arrays.stream(nums).sum();
    if (total % 2 != 0) return false;       // odd sum = impossible
    return canSubsetSum(nums, total / 2);   // reuse subset sum!
}

Target Sum

Problem: Given an array and a target, assign + or - to each number so they sum to the target. Count the number of ways.

Trick: If we add + to some numbers (set P) and - to others (set N), then P - N = target and P + N = total. So P = (total + target) / 2. This turns into a count subset sum problem!

function findTargetSumWays(nums, target) {
  const total = nums.reduce((a, b) => a + b, 0);
  if ((total + target) % 2 !== 0 || Math.abs(target) > total) return 0;
  const subsetSum = (total + target) / 2;
  const dp = new Array(subsetSum + 1).fill(0);
  dp[0] = 1;                                // one way to make sum 0
  for (const num of nums) {
    for (let s = subsetSum; s >= num; s--) {
      dp[s] += dp[s - num];                 // add number of ways
    }
  }
  return dp[subsetSum];
}

def find_target_sum_ways(nums, target):
    total = sum(nums)
    if (total + target) % 2 != 0 or abs(target) > total:
        return 0
    subset_sum = (total + target) // 2
    dp = [0] * (subset_sum + 1)
    dp[0] = 1                                # one way to make sum 0
    for num in nums:
        for s in range(subset_sum, num - 1, -1):
            dp[s] += dp[s - num]             # add number of ways
    return dp[subset_sum]

static int findTargetSumWays(int[] nums, int target) {
    int total = Arrays.stream(nums).sum();
    if ((total + target) % 2 != 0 || Math.abs(target) > total) return 0;
    int subsetSum = (total + target) / 2;
    int[] dp = new int[subsetSum + 1];
    dp[0] = 1;                                // one way to make sum 0
    for (int num : nums) {
        for (int s = subsetSum; s >= num; s--) {
            dp[s] += dp[s - num];
        }
    }
    return dp[subsetSum];
}

The Knapsack Family

Here’s the key insight — all these problems share the same skeleton:

Problem	Type	What changes?
0/1 Knapsack	Max value	Each item used at most once
Unbounded Knapsack	Max value	Items can repeat
Coin Change	Min count	Items can repeat, minimize instead of maximize
Subset Sum	Boolean	Can we hit exact target?
Partition Equal Subset	Boolean	Subset sum where target = totalSum/2
Target Sum	Count ways	Count subsets that hit target

When we see a problem with “choose items” + “capacity constraint”, think knapsack.