# How Sum

Updated: 01 February 2024

# Problem

Given a list of numbers write a function that will return the numbers from the array that can be summed to the given input if it is possible to sum the numbers to a given target, else return null. Each number can be used multiple times if needed. Can assume all numbers are positive

Some examples to consider:

```
canSum(7, [5,3,2,7]) = [2,5]
canSum(7, [2,4]) = null
```

We can follow a similar strategy as in the Can Sum example but here we will return an array of the values that added up the the desired result

# Base Implementation

The brute force solution looks like this:

`dynamic-programming/memoization/how-sum.ts`

```
export const howSum = (target: number, nums: number[]): number[] | null => {
if (target == 0) return [];
if (target < 0) return null;
for (const num of nums) {
const remainder = target - num;
const result = howSum(remainder, nums);
if (result) return [...result, num];
}
return null;
};
```

The above solution has a resulting time complexity of $O(n^m * m)$ with $n$ as the target and $m$ as the length of the array. We can technically also consider the result array which is $O(m)$ but that’s not very

# With memoization

In the context of this problem we have cases in which the `canSum`

function is being called with parameters that it has seen previously, we can apply the memoization as in other cases using this method

`dynamic-programming/memoization/how-sum-memo.ts`

```
type Memo = Record<number, number[] | null>;
export const howSum = (
target: number,
nums: number[],
memo: Memo = {}
): number[] | null => {
if (target in memo) return memo[target];
if (target == 0) return [];
if (target < 0) return null;
for (const num of nums) {
const remainder = target - num;
const remainderSum = howSum(remainder, nums, memo);
if (remainderSum) {
const returnValue = [...remainderSum, num];
memo[target] = returnValue;
return returnValue;
}
}
memo[target] = null;
return null;
};
```

In the resulting implementation the resulting complexity is $O(n * m^2)$ for time and $O(m^2)$ for space as we are now storing the result of each subcomputation to lookup later