Split money into every possible combination of coin denominations

Question

Background and objective of the code

Based on this Dev.to challenge, I wrote the Python code below (TIO link also available).

The task was to return the least number of coins in a given denomination to from a specified amount of money. I generalised this into a function that gives all possible combinations of coins that form a specified amount of money. From that, it was easy to write a oneliner function that does exactly that.

Review questions and review scope

I'm happy with the code that I wrote, and I'd really like some feedback to improve my (amateur) Python coding skills and style.

I'm interested in a general review of the code and functions that I've written: style, clarity, documentation, etc. I'm not specifically interested if there is an other/better way to give the answer to the challenge (although of course, also this feedback is welcome!).

Specific review questions that I can think of:

• is the split_in_denominations() function too long (too many lines)? If so: any suggestions to split it?
• Am I nesting too deep?
• Any comments/suggestions on the way I use a Numpy ndarray to store the intermediate results as a list of dicts?
• Although not the main (pun!) focus of my review question: is there a "better" way to show the test cases in main()? I'm aware of Python's unittest module, but that adds a considerable amount of boilerplate code...

Here is my code:

from typing import List, Dict
import numpy


def split_in_denominations(amount: int,
                           denominations: List[int]) -> List[Dict[int, int]]:
    """ Gives all distinct ways to express amount in items from denominations

    The algorithm used is to find all solutions for each smaller amount and
    each smaller list of (sorted) denominations. For example, for the amount
    of 3 and denominations [1, 2], the following Numpy array is created:

             Amount:  |     0     |     1     |     2     |     3     |
    Denominations:    +-----------+-----------+-----------+-----------+
                  [1] |[{1:0,2:0}]|[{1:1,2:0}]|[{1:2,2:0}]|[{1:3,2:0}]|
                [1,2] |[{1:0,2:0}]|[{1:1,2:0}]|[{1:2,2:0},|[{1:3,2:0},|
                      |           |           | {1:0,2:1}]| {1:1,2:1}]|
                      +-----------+-----------+-----------+-----------+

    This result array is built row by row from the top left to the bottom
    right. For each cell, only two (disjunct!) solution sets have to be
    considered: the one directly above (not using the current denomination)
    and the one 1 of the denomination value to the left. For that latter set,
    you just need to count one extra of denomination.

    Arguments:
        amount: integer value that has to be expressed in denominations
        denominations: list of values

    Returns:
        List with all unique dicts with denomination as key and the count
        of that denomination as value. The list is sorted by the sum of
        the count of all denominations (the least number of coins)

    Raises:
        ValueError is the amount can't be expressed by denominations

    Examples:
        >>> split_in_denominations(13, [1, 5, 10, 25])
        [{1: 3, 5: 0, 10: 1, 25: 0},   # 3 coins
         {1: 3, 5: 2, 10: 0, 25: 0},   # 5 coins
         {1: 8, 5: 1, 10: 0, 25: 0},   # 9 coins
         {1: 13, 5: 0, 10: 0, 25: 0}]  # 13 coins
    """

    # Template solution: an empty dict with count 0 of each denominations
    zero_denom = {d: 0 for d in denominations}

    # Edge case: amount == 0
    if amount == 0:
        return [zero_denom]

    # result array with all intermediate solutions
    result = numpy.ndarray((amount + 1, len(denominations)), dtype=list)

    # Loop over the sorted denominations
    for denom_idx, denom in enumerate(sorted(denominations)):
        for amount_idx in range(amount + 1):
            # In the first iteration of denom, fill the first row of result
            if denom_idx == 0:
                # Start with a copy of the template solution
                result[amount_idx, 0] = [dict(zero_denom)]

                # If amount is divisible by denom, add that solution
                if amount_idx % denom == 0:
                    result[amount_idx, 0][0][denom] = amount_idx // denom

            # Now add the other denominations one by one in each loop
            else:
                # Copy the results from the previous denomination list
                result[amount_idx, denom_idx] = list(result[amount_idx,
                                                            denom_idx - 1])

                # Extend the result with the solutions from
                # amount_idx minus denom, with 1 extra count of denom
                if amount_idx >= denom:
                    for solution in result[amount_idx - denom, denom_idx]:
                        new_solution = dict(solution)
                        new_solution[denom] += 1
                        result[amount_idx, denom_idx].append(new_solution)

    # Check if there is a result (result does not only contain the template)
    if result[amount, len(denominations) - 1] == [zero_denom]:
        raise ValueError(f"{amount} can't be expressed in {denominations}")

    return sorted(result[amount, len(denominations) - 1],
                  key=lambda s: sum(s.values()))


def least_num_denominations(amount: float,
                            denominations: List[float]) -> int:
    """ Gives the least number of denominations that is needed to sum to amount

    Arguments:
        amount: numeric value that has to be expressed in denominations
        denominations: list of values

    Returns:
        The least number of denominations.
        Returns None of there is no possible split into denominations.

    Examples:
        >>> least_num_denominations(4, [1, 2, 3])  # (2, 2) or (1, 3)
        2
    """
    return sum(split_in_denominations(amount, denominations)[0].values())


def main():
    denominations = {'coins1': [1, 5, 10, 25],
                     'coins2': [1, 2, 5, 10, 20, 50],
                     'coins3': [1, 5, 20, 25],
                     }

    cases = [('coins1', 13),  # 123),
             ('coins2', 13),  # 123),
             ('coins1', 75),
             ('coins2', 75),
             ('coins3', 40),
             ]

    for den_name, amount in cases:
        d = denominations[den_name]
        print(f'Least split of {amount} in {d} is: ' +
              f'{least_num_denominations(amount, d)} (there are ' +
              f'{len(split_in_denominations(amount, d))} ways to split)')


if __name__ == '__main__':
    main()