Published on

[Dynamic Programming] Best Sum

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

The function should return an array containing the shortest combination of numbers that add up to exactly the target sum.

If there is a tie for the shortest combination, you may return any one of the shortest.

Brute Force

const bestSum = (targetSum, numbers) => {
	// base cases
	if (targetSum === 0) return [];
	if (targetSum < 0) return null;

	// we should have some variable to hold the result for comparison
	let res = null;

	for(let num of numbers) {
		let remain = targetSum - num;

		// as usual, we find best sum for the remain
		let temp = bestSum(remain, numbers)
		if(temp !== null) {
			// first update or
			// later shorter update
			if(res === null || res.length > temp.length) {
				res = [...temp, num]
			}
		}
	}

	// either null or best result
	return res;
}

Memoization

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

	// base cases
	if (targetSum === 0) return [];
	if (targetSum < 0) return null;

	// we should have some variable to hold the result for comparison
	let res = null;

	for(let num of numbers) {
		let remain = targetSum - num;

		// as usual, we find best sum for the remain
		let temp = bestSumMemo(remain, numbers, memo)
		if(temp !== null) {
			// first update or
			// later shorter update
			if(res === null || res.length > temp.length + 1) {
				res = [...temp, num]
			}
		}
	}

	// either null or best result
	memo[targetSum] = res;
	return res;
}

Tabulation

const bestSumTab = (targetSum, numbers) => {
	// create table to store the default values
	let table = Array(targetSum + 1).fill(null)

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

	// iterate through the table
	for(let i = 0; i <= targetSum; i++) {
		// if table[i] is possible, table[i + num] is also possible
		if(table[i] !== null) {
			for(let num of numbers) {
				// table[i + num] may be null or undefined, ! is a trick here
				if(!table[i + num] || table[i + num].length > table[i].length + 1) {
					table[i + num] = [...table[i], num]
				}
			}
		}
	}

	return table[targetSum]
}

Reference