# Finding combination of coins that can produce a given sum

This function is checking, whether it has enough money in a list called self.deviceMoney to make change.

It works exactly the way I want, but only in case where not many coins are in self.deviceMoney. The algorithm is checking, if the list has enough coins to create some number, if yes remove that many coins from list.

Example

Number = 8
self.deviceMoney=[1,3,4,5,2]


Now, we can create this number from [3,4,1] or [5,3] etc.

List after operation self.deviceMoney == [5,2]

When I put into this list for example 200 coins, my program stops responding. I think, because a large amount of itertools.combinations. How can I optimize this function or resolve this problem to make the algorithm much better?

def changeOperation(self):
self.deviceMoney.sort()
tmpChange=int(self.change*100)
tmp=set()
# print(self.change)
print(self.deviceMoney)

if self.change > 0:
for i in range(1,len(self.deviceMoney)):
for j in itertools.combinations(self.deviceMoney,i):
if sum(j) == tmpChange:
print("tmp.append(list(j)): " +str(tmp))

if tmp:
a = next(iter(tmp))
print("a: " + str(a))
print("a= ",a)
for k in range(len(a)):
self.deviceMoney.remove(a[k])

print("deviceMoney: "+str(self.deviceMoney))

self.errorMessageBox("some string"))
else:
self.errorMessageBox("some string")
self.deviceMoney=[]

elif self.change == 0:
self.errorMessageBox("some string")

else:
pass

#prints for tests

• You create all the possible combinations and then you just use the first one. Seems you could just calculate the first one. But there's one possibly bigger issue which I guess is not really what it seems: If no combination was found, you "empty" the deviceMoney list (more specifically you assign a new empty list to self.deviceMoney). May 4, 2017 at 18:08
• You should check out this SO question. That might help May 4, 2017 at 18:09