Leetcode Question:

for each num in nums, you recursively make a new call for new target target-num. if you reach the leaf node, return empty array []. As you pull back to the root, add the num to the array in each level. While you make recursive call you should also be tracking the shortest path so far in memory and if you return a valid result array, compare the result with the shortest array so far and update the shortest array

from typing import List
class Solution:
    def coinChange(self, nums: List[int], target: int) -> int:
        def dfs(target, memo={}):
            # without memoization it wont pass 
            if target in memo:
                return memo[target]
            # base case changes depending on your logic
            if target == 0:
                return []
            if target < 0:
                return None
            shortest_combination = None
            for num in nums:
                remainder = target - num
                # this is where the decision tree is built
                result = dfs(remainder)
                # make sure not if result because result might be [] which yields to False
                if result != None:
                    # combination = result [num]
                    combination = [*result, num]
                    # when we get the first result, we assign shortest_combination to that result.
                    # so shortest_combination == None this will be true only once
                    if shortest_combination == None or len(combination) < len(shortest_combination):
                        shortest_combination = combination
            memo[target] = shortest_combination
            return shortest_combination

        return -1 if dfs(target) == None else len(dfs(target))