My own accounting python euler problem

[MRAB]

Ozz wrote:
> 
> Hi,
> 
>> 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
>>
> 
> Incidentally, I'm currently learning python myself, and was working on 
> more or less the same problem as an exercise;
> 
> For listing all different subsets of a list (This is what I came up 
> with. Can it be implemented shorter, btw?):
> 
> def subsets(L):
>         S = []
>         if (len(L) == 1):
>                 return [L, []]
>         else:
>                 for s in subsets(L[1:]):
>                         S.append(s)
>                         S.append(s + [ L[0]])
>         return S
> 
> Now, to use the above piece of code (after 'import subset'):
> 
>  >>> subset.subsets([4,7,8,2])
> [[2], [2, 4], [2, 7], [2, 7, 4], [2, 8], [2, 8, 4], [2, 8, 7], [2, 8, 7, 
> 4], [], [4], [7], [7, 4], [8], [8, 4], [8, 7], [8, 7, 4]]
>  >>> map(sum,subset.subsets([4,7,8,2]))
> [2, 6, 9, 13, 10, 14, 17, 21, 0, 4, 7, 11, 8, 12, 15, 19]
> 
> It's not a real solution yet, and as others have pointed out the problem 
> is NP complete but it might help to get you going.
> 
Here's my own take on it:

def list_possible_invoices(invoices, check):
     if check:
         # The check hasn't yet been fully consumed.
         for index, inv in enumerate(invoices):
             # If this invoice doesn't exceed the check then it consume 
some of the check.
             if inv <= check:
                 # Try to consume the remainder of the check.
                 for inv_list in list_possible_invoices(invoices[index + 
1 : ], check - inv):
                     yield [inv] + inv_list
     else:
         # The check has been fully consumed.
         yield []

invoices = [500, 400, 450, 200, 600, 700]
check = 600

# List all the possible subsets of invoices.
# Sorting the invoices first in descending order lets us reduce the 
number of possibilities to try.
for inv_list in list_possible_invoices(sorted(invoices, reverse=True), 
check):
     print inv_list