Time and Space complexity of Bestsum function

  python-3.x, space-complexity, time-complexity

I am only able to figure out to the point that the time complexity of the below given code should be O(len(nums)^m), but am not sure if the memoisation part inside the for loop or the copying of lists in the variable path makes any difference to the Time complexity.

def bestsum(x, nums, A={0:[]}):
    best_path = 'Null'
    #checking value of x in memo
    if x in A:
        return A[x]
    #base case
    elif x in nums:
        return [x]
    #main recursion
    elif x>0:
        for i in nums:
            # path = 'Null'
            r = bestsum(x-i, nums, A)            
            if r != 'Null':
                path = [i] + r
                if len(path)<len(best_path) or best_path=='Null':
                    best_path = path
            A[x] = best_path
        return best_path
    return 'Null'

As for the Space complexity, I am not able to figure out anything.

Source: Python-3x Questions

LEAVE A COMMENT