Last active
October 13, 2021 09:16
-
-
Save kishan-dhankecha/9c1fd5cb92187e541a9c068fa80a97e8 to your computer and use it in GitHub Desktop.
How 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 'howSum(targetSum, numbers)' that takes in a | |
/// targetSum and an array of numbers as arguments. | |
/// The function should return an array containing any combination of | |
/// elements that add up to exactly the targetSum. If there is no | |
/// combination that adds up to the targetSum, then return null. | |
/// If there are multiple combinations possible, you may return any | |
/// single one. | |
const howSum = (targetSum, numbers, memory = {}) => { | |
// Check in memory. | |
if (targetSum in memory) return memory[targetSum]; | |
// Return obvious values to stop recursion. | |
if (targetSum === 0) return []; | |
if (targetSum < 0) return null; | |
// Iterate through numbers array | |
for (let num of numbers) { | |
const remainder = targetSum - num; | |
const remainderResult = howSum(remainder, numbers, memory); | |
if (remainderResult !== null) { | |
// Store current value in memory. | |
memory[targetSum] = [...remainderResult, num]; | |
// Return value. | |
return memory[targetSum]; | |
} | |
} | |
// Store current value in memory. | |
memory[targetSum] = null; | |
// Return value. | |
return null; | |
} | |
console.log(howSum(7, [2, 3])); // [ 3, 2, 2 ] | |
console.log(howSum(300, [7, 14])); // null |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment