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
1export 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 and the time complexity is and the space complexity is
With memoization
We can implement memoizatio based on the target:
1type Memo = Record<number, number[] | null>;2
3export 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 and the space complexity of