Toy Combinations

toys.py

toys = [
    ("Yoyo", 122),
    ("Doll", 275),
    ("Duckie", 185),
    ("Tractor", 597),
    ("Airplane", 647),
    ("Ball", 216),
    ("Racecar", 713),
    ("Dog", 457),
    ("Jump Rope", 146),
    ("Car", 518),
    ("Elephant", 316),
    ("Bear", 489),
    ("Xylophone", 711),
    ("Tank", 645),
    ("Checkers", 477),
    ("Boat", 804),
    ("Train", 671),
    ("Jacks", 231),
    ("Truck", 621),
    ("Whistle", 98),
    ("Pinwheel", 87),
]

TOTAL = 4394
total_comb_count = 0
found_comb_count = 0


def find_combinations(amounts):
    global total_comb_count
    global found_comb_count
    cost = sum(amount * cents for amount, (_, cents) in zip(amounts, toys))
    if cost > TOTAL:
        return

    if len(amounts) == len(toys):
        total_comb_count += 1
        if cost == TOTAL:
            found_comb_count += 1
            print(
                f"{found_comb_count:>10}. "
                + ", ".join(
                    [f"{amount}*{toy_name}" for amount, (toy_name, _) in zip(amounts, toys) if amount != 0]
                )
            )
            if all(x <= 1 for x in amounts):
                print("   ==== HOORAY ====")
        return

    toy_name, cents = toys[len(amounts)]
    max_count = 1  # TOTAL // cents + 1
    for count in range(0, max_count + 1):
        find_combinations(amounts + [count])


find_combinations([])
print(f"Total Combinations: {total_comb_count}")