Skip to content

Instantly share code, notes, and snippets.

@iJustErikk
Created December 7, 2020 19:13
Show Gist options
  • Save iJustErikk/dd5b3f234946020cb0d666cfa596e8d1 to your computer and use it in GitHub Desktop.
Save iJustErikk/dd5b3f234946020cb0d666cfa596e8d1 to your computer and use it in GitHub Desktop.
fun fact, due to using tabulation and how I am not optimizing, this always gives the worst solution to the bestsum problem, if possible
const howSum = (goal, nums) => {
const table = new Array(goal + 1).fill(null);
table[0] = [];
// as long as there is a way to make table[i] (null check)
// there will be a way to make table[i] + num
// check bounds
for (let i = 0; i <= goal; i += 1) {
const currentArr = table[i];
if (currentArr) {
const sum = currentArr.reduce(((cur, total) => cur + total), 0);
for (let currentNum of nums) {
const newSum = sum + currentNum;
const newArr = currentArr.slice();
newArr.push(currentNum);
if (newSum <= goal) table[newSum] = newArr;
if (newSum === goal) return table[goal];
}
}
}
return table[goal];
};
console.log(howSum(7, [3,4]));
console.log(howSum(7, [3, 4, 5, 7])); //returns 3,4 or 7
console.log(howSum(7, [2, 4]));// returns null
console.log(howSum(300, [7, 14]));
console.log(howSum(373, [60, 4, 3, 2, 1]));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment