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

Start with the foundation – the base cases, which are the simplest solutions. Then, layer by layer, use the results of the previous layers to calculate the solutions for the next level. This way, we systematically build up the entire solution, avoiding redundant calculations and ensuring efficiency. It is like building a pyramid.

The underlying calculation logic remains fundamentally identical to the original recursive approach, albeit executed in reverse order.

# Python implementation

def check(ls, target):
  cache = [[False for _ in range(target + 1)] for _ in range(len(ls) + 1)]

  for i in range(len(ls) + 1):
    cache[i][0] = True

  for i in range(1, len(ls) + 1):
    for j in range(1, target + 1):
      if j < ls[i - 1]:
        cache[i][j] = cache[i - 1][j]
      else:
        cache[i][j] = cache[i - 1][j] or cache[i - 1][j - ls[i - 1]]

  return cache[len(ls)][target]

ls = [1, 5, 11, 5]

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

// Javascript implementation

function check(list, target) {
  const cache = Array.from(Array(list.length + 1), () => Array(target + 1).fill(false));

  for (let i = 0; i < list.length + 1; i++) {
    cache[i][0] = true;
  }

  for (let i = 1; i < list.length + 1; i++) {
    for (let j = 1; j < target + 1; j++) {
      if (j < list[i - 1]) {
        cache[i][j] = cache[i - 1][j]
      } else {
        cache[i][j] = cache[i - 1][j] || cache[i - 1][j - list[i - 1]];
      }
    }
  }

  return cache[list.length][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));

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

Hint