Published Nov 10, 2021
[
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.
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;
}
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;
}
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]
}