Best Sum

Updated: 01 February 2024

Problem

Essentially the same as the How Sum question but our goal here is to find the shortest array that yields the sum we are interested in. If there are multiple equally short options then we can take any one

Base Implementation

The solution to this is almost identical to the How Sum questio but we don’t early return when we find a solution of a subtree but instead we store the result of the best subtree as we iterate through

1
export const bestSum = (target: number, nums: number[]): number[] | null => {
2
  if (target == 0) return [];
3
  if (target < 0) return null;
4

5
  let shortest: number[] | null = null;
6

7
  for (let num of nums) {
8
    const remainder = target - num;
9
    const remainderCombination = bestSum(remainder, nums);
10

11
    if (remainderCombination) {
12
      const combination = [...remainderCombination, num];
13

14
      if (shortest == null || shortest.length > combination.length)
15
        shortest = combination;
16
    }
17
  }
18

19
  return shortest;
20
};

In the above solution with $m=target$ and $n=length of nums$ the time complexity is $O(n^m * m)$ and the space complexity is $O(m^2)$

With memoization

We can implement memoizatio based on the target:

1
type Memo = Record<number, number[] | null>;
2

3
export const bestSum = (
4
  target: number,
5
  nums: number[],
6
  memo: Memo = {}
7
): number[] | null => {
8
  if (target in memo) return memo[target]
9
  if (target == 0) return [];
10
  if (target < 0) return null;
11

12
  let shortest: number[] | null = null;
13

14
  for (let num of nums) {
15
    const remainder = target - num;
16
    const remainderCombination = bestSum(remainder, nums, memo);
17

18
    if (remainderCombination) {
19
      const combination = [...remainderCombination, num];
20

21
      if (shortest == null || shortest.length > combination.length)
22
        shortest = combination;
23
    }
24
  }
25

26
  memo[target] = shortest;
27
  return shortest;
28
};

The time complexity of this should now be $O(m^2 * n)$ and the space complexity of $O(m^2)$