[Dynamic Programming] Can Sum

Problem

Write a function canSum(targetSum, numbers) that takes in a target sum and an array of numbers as arguments.

The function should return a boolean indicating whether or not it is possible to generate the target sum using numbers from the array.

You may use an element of the array as many times as needed.

You may assume that all input numbers are nonnegative

Brute Force

Subtract one value from numbers and check if we can get the remainder.

const canSum = (targetSum, numbers) => {
    if(targetSum === 0) return true;
    if(targetSum < 0) return false;

    for(let num of numbers) {
        const remainder = targetSum - num
        if(canSum(remainder, numbers)) {
            return true
        }
    }

    return false;
}

Can Sum

Memoization

const canSumMemo = (targetSum, numbers, memo = {}) => {
    if(targetSum in memo) return memo[targetSum];

    if(targetSum === 0) return true;
    if(targetSum < 0) return false;

    // for each number, we subtract it from the target sum and check if it is possible to get the remainder.
    for(let num of numbers) {
        const remainder = targetSum - num;
        memo[targetSum] = canSumMemo(remainder, numbers, memo)
        if(memo[targetSum]) {
            return memo[targetSum]
        }
    }

    memo[targetSum] = false;
    return memo[targetSum];
}

Can Sum Memo

Tabulation

const canSumTab = (targetSum, numbers) => {
    const table = new Array(targetSum + 1).fill(false)
    table[0] = true

    for(let i = 0; i <= targetSum; i++) {
        // if current position is true, then the num later position is also true
        if(table[i] === true) {
            for(let num of numbers) {
                table[i + num] = true;
            }
        }
    }

    return table[targetSum]
}

Reference