Last active
October 13, 2021 09:17
-
-
Save kishan-dhankecha/7cedba0486d031a52b7ee22125901c59 to your computer and use it in GitHub Desktop.
Subset Sum function with memoization [JAVASCRIPT]
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
/// Write a function 'canSum( targetSum, numbers)' that takes in a | |
/// targetSum and an array of numbers as arguments. | |
/// The function should return a boolean indicating whether or not it | |
/// is possible to generate the targetSum using numbers from the array. | |
/// You may use an element of the array as many times as needed. | |
/// You may assume that all input numbers are nonnegative. | |
const canSum = (targetSum, numbers, memory = {}) => { | |
// Check in memory. | |
if (targetSum in memory) return memory[targetSum]; | |
// Return obvious values to stop recursion. | |
if (targetSum === 0) return true; | |
if (targetSum < 0) return false; | |
// Iterate through numbers array | |
for (let num of numbers) { | |
const remainder = targetSum - num; | |
if (canSum(remainder, numbers, memory) === true) { | |
// Store current value in memory. | |
memory[targetSum] = true; | |
// Return value. | |
return true; | |
}; | |
} | |
// Store current value in memory. | |
memory[targetSum] = false; | |
// Return value. | |
return false; | |
} | |
console.log(canSum(7, [3, 2])); // prints => true | |
console.log(canSum(30, [4, 12])); // prints => false |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment