How Sum with Tabulation

Updated: 01 February 2024

Problem

The same problem as the Memoization How Sum problem but we want to take a tabular approach which we can do as an adaptation of the Tabular Can Sum problem

For our purpose, let’s initialize the value as our return type of null and instead of storing a boolean we will store the current array value which has lead to that sum thus far

1
canSum(7,[5,3,4])-> [3,4]
2


3
i                  0    1     2     3     4     5     6     7
4
is sum=i possible  []   null  null  [3]   [4]   [5]   [3,3] [3,4]

At each step we replace the latter element and append the current value that we have

And so, our result is [3,4]

Tabulation Implementation

The implementation of this can be seen below:

dynamic-programming/tabulation/how-sum.ts
1
export const howSum = (target: number, nums: number[]): number[] | null => {
2
  const table = new Array<number[] | null>(target + 1).fill(null);
3
  table[0] = [];
4


5
  for (let index = 0; index <= target; index++) {
6
    const element = table[index];
7


8
    if (element) {
9
      for (const num of nums) {
10
        const nextIndex = index + num;
11
        if (nextIndex in table) {
12
          const nextValue = [...element, num];
13
          table[nextIndex] = nextValue;
14
        }
15
      }
16
    }
17
  }
18


19
  return table[target];
20
};

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

The reason we say m2m^2 and not mm in the time complexity is because of the array copy operation that we do to assign the latest value