The function should return an array containing the shortest combination of numbers that add up to exactly the target sum. If there are two (or more) possibilities, then return any one of them.
def bestSum(targetSum, numbers, memo = {}):
if targetSum in memo: return memo[targetSum]
if targetSum == 0: return []
if targetSum < 0: return None
shortestCombination = None
for num in numbers:
remainder = targetSum - num
remainderCombination = bestSum(remainder, numbers, memo)
if remainderCombination is not None:
remainderCombination.append(num)
if shortestCombination is None or len(remainderCombination) < len(shortestCombination):
shortestCombination = remainderCombination
memo[targetSum] = shortestCombination
return memo[targetSum]
Input Call: bestSum(4, [2,1])
Output: [2, 2, 1]
Expected Output: [2,2]