[Tutor] Euler Spoiler

[Keith Winston]

I'm working through some of the Project Euler problems, and the
following might spoil one of the problems, so perhaps you don't want
to read further...


The problem relates to finding all possible combinations of coins that
equal a given total. I'm basically brute-forcing it, which is probably
not the way to go, but has already taught me a good bit about sets,
tuples, and iterators, so... so far so good.

However, after all the refactoring I can think of, I can't get it past
a 3-coin list without it bogging down.

I'm sure there are wholly different approaches, feel free to hint at
them, but my real question is: is there any further fine-tuning of my
approach (or any outright problems with it) that would be instructive?
Thanks!

Also: I think it might have worked better with lists that tuples,
though I don't really understand why, unless I misunderstand speed or
memory management issues (or something else).

from itertools import combinations

coins = [100, 50, 20]  # should include 1, 2, 5, 10 (plus one 200 combo)
ans = set()
goal = 200
tcombo = ()

# Iterate over all possible length combinations of coins
for i in range(len(coins)):
    print(i)
    # For each unique combo of coins, and...
    for combo in combinations(coins, i+1):
        tcombo = ()
        # For each coin in that combo...
        for coin in combo:
            # create a new tuple of as many of those coins as
            # it would take to reach the goal
            tcombo = tcombo + (coin,) * int(goal/coin)
            # with this new extended list, generate all possible
length combinations
            for k in range(len(tcombo)):
                for c in combinations(tcombo, k + 1):
                    if sum(c) == goal:
                        ans = ans | {c}

print(ans)


-- 
Keith