My Solution

.py

# This is an O(n^2 * m) runtime, but it can be decreased to O(n*m)
from typing import List

coin_list = [1,4,5]
target = 12

def coin_solution_hard(coin_list_start: List[int], target: int) -> int:
    """
    Input: coin_list_start = list of sorted coin values in a List \\
    Output: all_coin_combos = Nested List of all combinations of coins that equal the target.
    """
    original_target: int = target
    all_coin_combos: List[int] = []
    coin_count: List[int] = []
    index: int = len(coin_list_start)-1
    original_index: int = index
    speed_count = 0

    for i in range(index):
        speed_count +=1
        while target != 0:
            speed_count +=1
            if target - coin_list_start[index-i] >= 0:
                target -= coin_list_start[index-i]
                coin_count.append(coin_list_start[index-i])
            else:
                index -= 1
        index = original_index
        all_coin_combos.append(coin_count)
        coin_count = []
        target = original_target
    print("speed count #1 ", speed_count)
    return all_coin_combos

def min_coin_combo(all_coin_combos: List[List[int]]):
    min_coin_combo: List[int] = None
    speed_count = 0
    for i in range(len(all_coin_combos)):
        speed_count += 1
        if min_coin_combo == None:
            min_coin_combo = all_coin_combos[i]
        else:
            if len(all_coin_combos[i]) < len(min_coin_combo):
                min_coin_combo = all_coin_combos[i]
    print("speed count #2", speed_count)
    return min_coin_combo


combos = coin_solution_hard(coin_list, target)
print(min_coin_combo(combos))