Last active
December 5, 2020 02:12
-
-
Save iJustErikk/08620336e55cce68d727495e14404fd2 to your computer and use it in GitHub Desktop.
forgot to memoize false values
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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