In the accounting department I am working for we are from time to time
confronted to the following problem:

A customer sends us a check for a given amount, but without specifying
what invoices it cancels. It is up to us to find out which ones the
payment corresponds to.

For example, say that the customer has the following outstanding
invoices:  $300, $200, $50; and say that the check is for $250. This
time it is clear, the customer is paying bills $200 and $50.

However, let's now say that the outstanding invoices are $300, $200,
$100 and that the check is for $300. In this case there are already
two possibilities. The customer is paying the $300 invoice or the $200
and $100. In other words, there is more than one solution to the
problem.

My first question is:
1. given a list of invoives I=[500, 400, 450, 200, 600, 700] and a
check Ch=600
how can I print all the different combinations of invoices that the
check is possibly cancelling

1.a. first approach using "brute force", that is, exploring all
different combinations: every single invoice, all of 2-element tuples,
3-element tuples, etc...

1.b can all the solutions be found without exploring all possible
combinations? some problems can be solved by discarding some invoices,
for example those whose amounts are greater than the amount of the
check. Any ideas?

My second question is:
2. this time there are also credit notes outstanding, that is,
invoices with negative amounts. For example,  I=[500, 400, -100, 450,
200, 600, -200, 700] and a check Ch=600

2.a  is the "brute force" method used in 1.a still applicable now that
"I" contains negative values?

2.b  same as 1.b.  However, this time I can imagen that the number of
invoices that can be discarded is a lot more reduced.

I am a fan of Python, which I find very elegant, powerful and easy to
develop with. I would like to find answers to the problems described
above, partially because I am still learning python, and I would like
to make use of it.

Can anybody help?
-- 
http://mail.python.org/mailman/listinfo/python-list