Subset Sum Problem

The problem

Implement `subsetSumProblem(nums, target)`: given an array of non-negative integers, return whether any subset of them sums to exactly `target`. Each number may be used at most once.

`nums = [2, 3, 7, 8, 10], target = 11` returns `true` — `[3, 8]` sums to `11`. `target = 6` returns `false` — no combination of those five numbers lands on `6`, even though several land near it.

The approach

This is 0/1 knapsack with the objective removed. In `knapsackTopDown`, `memo[i][j]` held the best value achievable from the first `i` items within capacity `j`; here it holds whether sum `j` is *reachable* using the first `i` numbers. The item loop, the capacity loop and the `nums[i-1] <= j` guard are all identical — only what a cell stores changes, and with it the operator that combines the two choices.

`Math.max(take, skip)` becomes `skip || take` for the reason the objective changed: with values, both branches produce a number and the bigger one wins; with reachability, both produce a boolean and either one being `true` settles it. There's nothing to compare, so the max collapses into a logical or — and the short-circuit means `memo[i-1][j-nums[i-1]]` isn't even evaluated once the skip branch already says `true`.

The two initialisation loops encode the base cases and they disagree at exactly one cell. `memo[0][j] = false` says an empty prefix can't reach any positive sum; `memo[i][0] = true` says every prefix can reach `0` by taking nothing. They collide at `memo[0][0]`, and the order matters — the column loop runs second, so `true` wins, which is the correct answer: the empty subset sums to zero. Swap the two loops and the entire table is built on a `false` that shouldn't be there.

`nums[i-1] <= j` is the same fits-or-doesn't guard as the knapsack's weight check, doing the same job: it keeps `j - nums[i-1]` from going negative. A number bigger than the current target simply can't be part of a subset summing to it, so the only reachable option is whatever the previous row already knew.

The solution

export function subsetSumProblem(nums, target) {
    const memo = Array.from({ length: nums.length + 1 }, () => Array(target + 1).fill(null))

    // initialize the first row with true
    for (let j = 0; j <= target; j++) {
        memo[0][j] = false
    }

    // initialize the first column with true
    for (let i = 0; i <= nums.length; i++) {
        memo[i][0] = true
    }

    // fill the memo table
    for (let i = 1; i <= nums.length; i++) {
        for (let j = 1; j <= target; j++) {
            if (nums[i-1] <= j) {
                memo[i][j] = memo[i-1][j] || memo[i-1][j-nums[i-1]]
            } else {
                memo[i][j] = memo[i-1][j]
            }
        }
    }

    // return the result
    return memo[nums.length][target] === true
}

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