Skip to content

Instantly share code, notes, and snippets.

@kishan-dhankecha
Last active October 13, 2021 09:16
Show Gist options
  • Save kishan-dhankecha/9c1fd5cb92187e541a9c068fa80a97e8 to your computer and use it in GitHub Desktop.
Save kishan-dhankecha/9c1fd5cb92187e541a9c068fa80a97e8 to your computer and use it in GitHub Desktop.
How Sum function with memoization [JAVASCRIPT]
/// 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