Skip to content

Instantly share code, notes, and snippets.

@iJustErikk
Last active December 5, 2020 02:12
Show Gist options
  • Save iJustErikk/08620336e55cce68d727495e14404fd2 to your computer and use it in GitHub Desktop.
Save iJustErikk/08620336e55cce68d727495e14404fd2 to your computer and use it in GitHub Desktop.
forgot to memoize false values
// t/f
// use number from numbers as many times as needed to construct targetSum
const canSum = (targetSum, numbers, memo = new Map()) => {
const key = `${targetSum}`;
if (targetSum === 0) return true;
if (memo.has(key)) return memo.get(key);
for (let currentNum of numbers) {
const after = targetSum - currentNum;
if (after < 0) continue;
const can = canSum(after, numbers, memo);
memo.set(key, can);
if (can) return true;
}
memo.set(targetSum, false);
return memo.get(targetSum);
};
console.log(canSum(7, [3, 4, 5, 7]));
console.log(canSum(7, [2, 4]));
console.log(canSum(7, [10,20,3,14,5,60,70, 140, 30, 40, 50])); //false
// canSum(7, [3, 4, 5, 7]) -> true, as 3 + 4 = 7 or 7 = 7
// canSum(7, [2, 4]) -> false
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment