Can Sum with Tabulation

Updated: 01 February 2024

Problem

The same problem as the Memoization Can Sum problem but we want to take a tabular approach

When using a table we should consider a table size based on the target number we want for this problem, in this context we will use the array size as target+1. For initialization we consider the resulting type, in this case we want a boolean so we initialize the entire array to false

In this case we also consider that the sum of 0 is always true, so we set this in the table. Our initial setup of our table then represents:

1
canSum(7,[...])
2


3
i                  0 1 2 3 4 5 6 7
4
is sum=i possible  T F F F F F F F

Now we will iterate through each section checking if any given value is possible using any ofthe other numbers we have by setting that sum as true. Furthermore, we can only evaluate if a sum is possible by updating data based on a sum that is already possible

The overall idea of how we transition state can be seen below:

Tabulation Implementation

The implementation of this can be seen below:

dynamic-programming/tabulation/can-sum.ts
1
export const canSum = (target: number, nums: number[]): boolean => {
2
  const table = new Array<boolean>(target + 1).fill(false);
3
  table[0] = true;
4


5
  for (let index = 0; index <= target; index++) {
6
    if (table[index]) {
7
      for (const num of nums) {
8
        const nextIndex = index + num;
9
        if (nextIndex in table) table[nextIndex] = true;
10
      }
11
    }
12
  }
13


14
  return table[target];
15
};

In the above, the time complexity O(m∗n)O(m*n) and space complexity O(m)O(m)