Question

Python3 *Use Recursion*

Write a function called smallest_sum(A,L) where A is the value and L is a list of ints.

smallest_sum should return the length of the smallest combinations of L that add up to A

if there are no possible combinations then float("inf") is returned.

Examples

smallest_sum(5, [2, 3]) == 2

smallest_sum(313, [7, 24, 42]) == 10

smallest_sum(13, [8, 3, 9, 6]) == float(‘‘inf’’)

No Loops and map/reduce functions are allowed

Answer 1

python code with explanation in comments (code to copy)

# This recursive function looks for all possible combinations from the list
# L which can make up to A
# The parameters cur_pos represents the current element we are going to add or not add
# cur_sum represents the current sum after adding previous elements
# cur_count represents how many elements we have added so far
def recursion(L, A, cur_pos,cur_sum, cur_count):
    # base case, if we have found a combination thnen return the 
    # number of elements added so far
    if(cur_sum==A):
        return cur_count
    # If our array is over or our current sum has exceeded required sum which is A
    # we can exit the function
    if cur_pos==len(L) or cur_sum>A:
        return float("inf")
    # If we are here, it means that we still need to add more numbers
    # we have two choice either add the current number
    # or not add it
    # Remember that we can use numbers multiple times so if we add the number we dont increase
    # cur_pos but if we dont add it then we increment cur_pos to process next element
    # we call both functions and since we are looking for the minimum we return min of them
    return min(recursion(L, A,cur_pos, cur_sum+L[cur_pos], cur_count+1), recursion(L, A,cur_pos+1, cur_sum, cur_count))

def smallest_sum(A, L):
    return recursion(L, A, 0, 0, 0)

print("smallest_sum(5, [2, 3]) == ", smallest_sum(5, [2, 3]))
print("smallest_sum(313, [7, 24, 42]) == ", smallest_sum(313, [7, 24, 42]))
print("smallest_sum(13, [8, 3, 9, 6]) == ", smallest_sum(13, [8, 3, 9, 6]))

python code screenshot

Code Output Screenshot

Let me know in the comments if you have any doubts.
Do leave a thumbs up if this was helpful.