I tried to solve Best Sum problem in Python but I am not able to figure out the issue, please suggest what is wrong

Question

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]

Answer 1

So the solution was pretty simple but I didn't notice at that time. Instead of copying the list like shortestCombination = remainderCombination we should use shortestCombination = remainderCombination.copy() so that the shortestCombination and remainderCombination don't point to the same List in memory.

Here is the correct code with good performance as well

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.copy()
            
    memo[targetSum] = shortestCombination
    return shortestCombination
    
if __name__ == '__main__':
    print(bestSum(4, [2, 1]))    #Output  [2, 2] 

    print(bestSum(300, [2, 7]))
    #Output 2, 2, 2, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 
    #       7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7]

Answer 2

You may change this line:

    if targetSum in memo: 
        return memo[targetSum]

into:

    if targetSum in numbers: 
        return [targetSum]

Why ? Because until the last recursion, memo is still empty, so you never return the list with the target sum.

Here is your code with some improvements, mostly style in order to fit PEP8:

def best_sum(target_sum, numbers, memo={}):
    if target_sum in numbers:
        return [target_sum]
    if target_sum == 0:
        return []
    if target_sum < 0:
        return None

    shortest_combination = None
    for num in numbers:
        remain = target_sum - num
        
        reminder_combination = best_sum(remain, numbers, memo)

        if reminder_combination is not None:
            reminder_combination.append(num)
            if shortest_combination is None or len(reminder_combination) < len(shortest_combination):
                shortest_combination = reminder_combination

    memo[target_sum] = shortest_combination
    return shortest_combination


if __name__ == '__main__':
    print(best_sum(4, [2, 1]))
    # [2, 2]

Answer 3

So I think you missed a couple of more list copies and that might cause your memo memory to be wrong. Please try this one, I am sure this will give results which your algorithm misses.

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:
            combination = remainderCombination + [num]
            if shortestCombination is None or len(combination) < len(shortestCombination):
                shortestCombination = combination.copy()

    print(str(targetSum) + "---------" + str(shortestCombination))
    if shortestCombination:
        memo[targetSum] = shortestCombination.copy()
    else:
        memo[targetSum] = None
    return shortestCombination

Answer 4

We need to have a memo for reducing runtime. But we are dealing with lists. So when we are returning a list, we should use a copy(), instead of just returning a reference. Memo-isation gives much better performance. While returning actual copies of the intermediate lists ensures we are not dealing with stale data. Also, in python list copy can be done using slicing. Hence a = [1,2,3] b = a[:] is equivalent to b = a.copy(). Updating my code to reflect the same.

This is the correct answer, both for performance and proper copying:

def bestSum(targetSum, numbers, memo):
    if targetSum in memo:
        return memo[targetSum][:]
    if targetSum == 0:
        return []
    if targetSum < 0:
        return None

    shortestCombi = None

    for num in numbers:
        remainder = targetSum - num
        remainderCombi = bestSum(remainder, numbers, memo)

        if remainderCombi is not None:
            remainderCombi.append(num)
            if shortestCombi is None or len(remainderCombi) < len(shortestCombi):
                shortestCombi = remainderCombi[:]

    if shortestCombi:
        memo[targetSum] = shortestCombi[:]
    else:
        memo[targetSum] = None
    
    return shortestCombi

Answer 5

def bestSum(total,ls, memo={}):
    if total in memo:
        return memo[total]
    if total==0:
        return []
    if total<0:
        return None
    shortestSum=None
    for num in ls:
        remainder=total-num
        res=bestSum(remainder,ls,memo)
        if res != None:
            res=res.copy()+[num]
            if shortestSum ==  None or len(shortestSum) > len(res):
                shortestSum=res
    memo[total]=shortestSum           
    return shortestSum