Partition a set into two subsets of equal sum (Memoization)

Given a list of numbers, check if it can be partitioned into two parts such that the sum of elements in both parts is the same.

Hint

This algorithm uses memoization to improve performance. It's same as the recursive version of Partition a set into two subsets of equal 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, target):
  if target == 0:
    return True

  if ls[0] > target:
    return False
  
  global cache
  if not cache:
    cache = [{} for _ in range(len(ls))]

  if target not in cache[len(ls) - 1]:
    cache[len(ls) - 1][target] = check(ls[1:], target - ls[0]) or check(ls[1:], target)

  return cache[len(ls) - 1][target]

ls = [1, 5, 11, 5]

print(False if sum(ls) % 2 != 0 else check(ls, sum(ls) // 2))

let cache = null;

function check(list, target) {
  if (target === 0) {
    return true;
  } 

  if (list[0] > target) {
    return false;
  }

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

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

  return cache[list.length - 1][target];
}

const list = [1, 5, 11, 5];
const sum = list.reduce((c, i) => c + i, 0);

console.log((sum % 2 != 0) ? false : check(list, sum / 2));