0/1 Knapsack — Memoized Recursion

The problem

Same 0/1 knapsack as the previous entry — maximum value from a subset of items fitting a capacity, each item usable at most once — but fast enough to run on inputs where the naive recursion doesn't finish.

The reason the recursion is so wasteful: skipping item A then taking item B lands on the same `(index, capacity)` state as taking B then skipping A, and the plain version solves that shared subtree twice. Multiply that across every branch and most of the exponential work is duplicate.

The approach

The cache key has to be exactly the parameters that change across calls, and here that's `index` and `capacity` — `weights` and `values` are the same arrays on every call, so they carry no state. Two changing parameters means a two-dimensional table, sized `(weights.length + 1) x (capacity + 1)` because both indexes are inclusive of their upper bound.

`null` is the sentinel for 'not computed yet' rather than `0`, and that distinction matters: `0` is a perfectly valid answer (an item that fits nothing, a capacity that fits nothing), so filling the table with `0` would make every genuine zero look like a cache hit — the recursion would return early with an answer it never computed. Any legal result must not be usable as the empty marker.

Three lines change from the plain version and nothing else: a `memo` parameter threaded through the helper, an early return when `memo[index][capacity] !== null`, and every `return expr` becoming `memo[index][capacity] = expr` followed by a return. The two choices, the fits-or-doesn't guard and the base case are untouched — memoization is a wrapper around the logic, not a rewrite of it.

The base case relaxed from `index === 0 || capacity === 0` to `index <= 0 || capacity <= 0`, which is defensive rather than necessary: the include branch already only recurses when `currentWeightOfItem <= capacity`, so `capacity` can't go negative. The `<=` form costs nothing and means a negative never silently indexes into `memo[-1]` if that guard is ever edited.

The result is the number of distinct `(index, capacity)` pairs — `n * capacity` — each computed once at `O(1)` cost. The recursion tree still exists, but every repeated subtree is now a single array read instead of a full re-descent.

The solution

export function knapsackRecursionMemoized(weights, values, capacity) {
    const memo = Array.from({ length: weights.length + 1 }, () => Array(capacity + 1).fill(null))
    return knapsackRecursionHelper(weights, values, capacity, weights.length, memo)
}

function knapsackRecursionHelper(weights, values, capacity, index, memo) {
    if (index <= 0 || capacity <= 0) {
        return 0
    }

    if (memo[index][capacity] !== null) {
        return memo[index][capacity]
    }

    const currentWeightOfItem = weights[index-1]
    const currentValueOfItem = values[index-1]
    if (currentWeightOfItem <= capacity) {
        memo[index][capacity] = Math.max(
            currentValueOfItem + knapsackRecursionHelper(weights, values, capacity - currentWeightOfItem, index - 1, memo), // include the item
            knapsackRecursionHelper(weights, values, capacity, index - 1, memo)) // exclude the item
        return memo[index][capacity]
    }
    memo[index][capacity] = knapsackRecursionHelper(weights, values, capacity, index - 1, memo)
    return memo[index][capacity]
}

Time O(n * capacity)Space O(n * capacity)