This sounds very much like a problem that demands trying to break the problems down into subproblems, and then applying a "dynamic-programming approach" to make it fairly easy to get an efficient solution. Such problems that are amendable to this approach have a "substructure" to them so that the main problem breaks down into smaller versions of the same problem.
As an example, Problem 15 on Lattice paths is a good one: http://projecteuler.net/problem=15 Here, the problem is asking: count how many paths there are in the n*n grid. A sub-problem of this is: count how many paths there are in the (n-1)*n graph, and count how many paths there are in the N*(n-1) grid. Why are those particular subproblems interesting? Because if you have the answer for the (n-1)*n and the n*(n-1), then you add the results of those two together, and you get the answer for the original n*n case! Another example of a dynamic programming situation is in Problem 18, http://projecteuler.net/problem=18 where we can decompose the problem of trying to find the path that maximizes the sum from the triangle as a whole to the sub-triangles on the left and right hand sides. In your problem statement, you're trying to answer the question: Given some goal g, find all the ways to break change. A subproblem of this is: Given some goal (g - x) for each x in the denominations, find all the ways to break change. That is, a trick to solving the problem is to treat 'goal' as a variable, part of the problem statement that can be changed. Are you familiar with the dynamic programming approach? I'm sure folks here would be happy to talk about it more and show concrete examples; it's a very powerful tool. _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
