Subset sum (Memoization)

Given a list[] of non-negative integers and a value sum, check if there is a subset of the given list whose sum is equal to the given number.

Hint

This algorithm uses memoization to improve performance. It's same as the recursive version of Subset sum, but with a special 'cache' to store results. The 'cache key' is crucial. It's how we identify and store past results. Sometimes we need one key, sometimes multiple keys. We add code to:

• Initialize cache to store results.
• Using the key to check cached result. If the result is not found in the cache, do the calculation and save the result in cache.
• Return the cached result.

• Python
• Javascript
•  Run

cache = None

def check(ls, total):
  if len(ls) <= 0:
    return False

  if total == 0:
    return True

  global cache
  if not cache:
    cache = [{} for _ in range(len(ls))]

  i = len(ls) - 1
  if total not in cache[i]:
    if ls[0] > total:
      cache[i][total] =  check(ls[1:], total)

    cache[i][total] = check(ls[1:], total - ls[0]) or check(ls[1:], total)
  
  return cache[i][total]

ls = [3, 34, 4, 12, 5, 2]
total = 9

print(check(ls, total))

let cache = null;

function check(list, total) {
  if (list.length <= 0) {
    return false;
  }

  if (total === 0) {
    return true;
  }

  if (!cache) {
    cache = Array(list.length).fill({});
  }

  let i = list.length - 1;

  if (cache[i][total] === undefined) {
    if (list[0] > total) {
      cache[i][total] = check(list.slice(1), total); 
    }
  
    cache[i][total] = check(list.slice(1), total - list[0]) || check(list.slice(1), total);
  }

  return cache[i][total];
}

const list = [3, 34, 4, 12, 5, 2];
const total = 9;

console.log(check(list, total));