Problem 3.3: Count Coins Tree (100 pts)

Nolan wants to help his friends learn tree recursion! They don't really understand all the recursive calls and how they work, so Nolan decides to generate a tree to show the recursive calls in a tree recursion. As a demonstration, he picks the count_coins problem, which is a simplified version of count_change problem in hw03. The following code is his implementation of count_coins problem.

def count_coins(total, denominations):
    """
    Given a positive integer `total`, and a list of denominations,
    a group of coins make change for `total` if the sum of them is `total` 
    and each coin is an element in `denominations`.
    The function `count_coins` returns the number of such groups. 
    """
    if total == 0:
        return 1
    if total < 0:
        return 0
    if len(denominations) == 0:
        return 0
    without_current = count_coins(total, denominations[1:])
    with_current = count_coins(total - denominations[0], denominations)
    return without_current + with_current

Implement count_coins_tree, which takes in a non-negative integer total and a list denominations, and returns a tree representing the recursive calls of count_coins.

Since the recursive tree is usually huge, Nolan decides to include only the recursive calls that eventually lead to a valid way of making change.

The leaves of tree count_coins_tree(15, [1, 5, 10, 25]) are listed below:

• 15 1-cent coins
• 10 1-cent, 1 5-cent coins
• 5 1-cent, 2 5-cent coins
• 5 1-cent, 1 10-cent coins
• 3 5-cent coins
• 1 5-cent, 1 10-cent coin

Note: The label of the tree should be a string.

def count_coins_tree(total, denominations):
    """
    >>> count_coins_tree(1, []) # Return None since there is no way to make change with empty denominations
    >>> t = count_coins_tree(3, [1, 2]) 
    >>> print(t) # 2 ways to make change for 3 cents
    3, [1, 2]
      2, [1, 2]
        2, [2]
          1
        1, [1, 2]
          1
    >>> # 6 ways to make change for 15 cents
    >>> t = count_coins_tree(15, [1, 5, 10, 25]) 
    >>> print(t)
    15, [1, 5, 10, 25]
      15, [5, 10, 25]
        10, [5, 10, 25]
          10, [10, 25]
            1
          5, [5, 10, 25]
            1
      14, [1, 5, 10, 25]
        13, [1, 5, 10, 25]
          12, [1, 5, 10, 25]
            11, [1, 5, 10, 25]
              10, [1, 5, 10, 25]
                10, [5, 10, 25]
                  10, [10, 25]
                    1
                  5, [5, 10, 25]
                    1
                9, [1, 5, 10, 25]
                  8, [1, 5, 10, 25]
                    7, [1, 5, 10, 25]
                      6, [1, 5, 10, 25]
                        5, [1, 5, 10, 25]
                          5, [5, 10, 25]
                            1
                          4, [1, 5, 10, 25]
                            3, [1, 5, 10, 25]
                              2, [1, 5, 10, 25]
                                1, [1, 5, 10, 25]
                                  1
    """
    "*** YOUR CODE HERE ***"

Hint1: The implementation of count_coins_tree will follow a similar logic to count_coins defined above.

Hint2: Return None if it's no way to make change, but do not include None in the tree.