# 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

```
canSum(7,[5,3,4])-> [3,4]
i 0 1 2 3 4 5 6 7
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`

```
export const howSum = (target: number, nums: number[]): number[] | null => {
const table = new Array<number[] | null>(target + 1).fill(null);
table[0] = [];
for (let index = 0; index <= target; index++) {
const element = table[index];
if (element) {
for (const num of nums) {
const nextIndex = index + num;
if (nextIndex in table) {
const nextValue = [...element, num];
table[nextIndex] = nextValue;
}
}
}
}
return table[target];
};
```

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

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