# 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:

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:

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

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