Skip to content

Instantly share code, notes, and snippets.

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