Skip to content

Instantly share code, notes, and snippets.

@iJustErikk
Created December 7, 2020 19:39
Show Gist options
  • Save iJustErikk/ab8dd6526d4585e68aa8ba435fd3fa1d to your computer and use it in GitHub Desktop.
Save iJustErikk/ab8dd6526d4585e68aa8ba435fd3fa1d to your computer and use it in GitHub Desktop.
const bestSum = (goal, nums) => {
const table = new Array(goal + 1).fill(null);
table[0] = [];
// want to update table only if our new array is better
for (let i = 0; i <= goal; i += 1) {
const currentArr = table[i];
if (!currentArr) continue;
for (let currentNum of nums) {
const newSum = i + currentNum;
if (newSum > goal) continue;
const newArr = [...currentArr, currentNum];
const oldArrAtNewSum = table[newSum];
if (!oldArrAtNewSum) table[newSum] = newArr;
}
}
return table[goal];
};
console.log(bestSum(8, [2, 5, 3])); // -> 5,3
console.log(bestSum(20, [1,2,3,4,5]))
console.log(bestSum(125, [1,2,4,8,16,32]));
console.log(bestSum(9, [4]));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment