[Dynamic Programming] How Sum

Problem

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

The function should return an array containing any combination of elements that add up to exactly the target sum. If there is no combination that adds up to the target sum, then return null.

If there are multiple combinations possible, you may return any single one.

Brute Force

const howSum = (targetSum, numbers) => {
	// base cases
	// return different values for different base cases
	if(targetSum === 0) return []
	if(targetSum < 0) return null

	// reduce the problem size and solve the sub problem
	for (let num of numbers) {
		let remainValue = targetSum - num
		let temp = howSum(remainValue, numbers)
		if(temp !== null) {
			return [...temp, num]
		}
	}

	return null
}

Memoization

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

	// base cases
	// return different values for different base cases
	if(targetSum === 0) return []
	if(targetSum < 0) return null

	// reduce the problem size and solve the sub problem
	for (let num of numbers) {
		let remainValue = targetSum - num
		let temp = howSumMemo(remainValue, numbers, memo)
		if(temp !== null) {
			memo[targetSum] = [...temp, num]
			return memo[targetSum]
		}
	}

	memo[targetSum] = null
	return null
}

Tabulation

const howSumTab = (targetSum, numbers) => {
	// create a table for tabulation
	// default null assuming the target sum is not possible to get
	let table = Array(targetSum + 1).fill(null)

	// target sum 0 is possible with empty array
	table[0] = []

	// we iterate through the table
	for(let i = 0; i <= targetSum; i++) {
		// if the value is not null, it means the current target sum (index) is possible
		if(table[i] !== null) {
			for(let num of numbers) {
				// then the num later target sum is also possible
				table[i + num] = [...table[i], num]
			}
		}
	}

	return table[targetSum]
}

Reference