pythonalgorithmrecursiondynamic-programmingcoin-change

# How to find subsets from a set that product equals the target?

Let us say we have a list and target of:
list: `[1,2,3,4,5]` and target: `20` and we want to find total combinations to reach this, with multiplication, which is: `[1,4,5]`, `[4,5]`, `[2,5,2]`, `[1,2,2,5]` I did this code, but I can't seem to know how to remove the ones so I have them too, I mean that I receive: `[1,4,5]`, `[1,2,2,5]`.
But without `[1]`, I can't seem to get it, I tried to "cheat" somehow to get it, but I can't since my code doesn't fit for it...

``````def Coin(target, lst, temp=[], comb=[]):
if target == 1:
comb.append(temp)
return comb
if len(lst) == 0:
return []
if target >= lst[0]:
if lst[0] > 1:
take=Coin(target/lst[0],lst,temp+[lst[0]],comb)
dont_take=Coin(target,lst[1:],temp,comb)
else:
take_1 = Coin(target, lst[1:], temp + [1], comb)
return take_1
return take
return comb

print(Coin(20, [1,2,3,4,5], [], []))
[[1, 2, 2, 5], [1, 4, 5]]
``````

How to add the parts without 1? I don't need a solution, since as said, not homework, but practice for exam. Just a clue will be enough, I want to find it myself, but I need a clue for it.

Solution

• Edit: The rules for the question is:

1. Positive integers only ( 0 not allowed ).

2. Number can appear once only ( at input ).

3. can not repeat numbers on list. EG: [1,2,3,4], n=12 >> [1,12], [12,1], [3,4], [2,6], [1,3,4], [1,2,6].
NOT: [1,2,2,3], [2,2,3]

4. That is all I guess.

``````def coin_change_MULTI(num, lst):
if num == 1 and 1 not in lst:
return []
return Coin_MULTI(num, sorted(lst), [], [])
def Coin_MULTI(target, lst, temp=[], comb=[]):
if target == 1:
if big_than_target(1, lst):
return [[1]]
comb.append(temp)
return comb
if len(lst) == 0: return []
if target >= lst[0]:
if lst[0] > 1:
take=Coin_MULTI(target/lst[0],lst[1:],temp+[lst[0]],comb)
dont_take=Coin_MULTI(target,lst[1:],temp,comb)
return comb
else:
take_1 = Coin_MULTI(target, lst[1:], temp + [1], comb)
dont_take_1 = Coin_MULTI(target, lst[1:], temp, comb)
return comb
return take + dont_take
return comb

print(coin_change_MULTI(12, [2,4,6,12,7,3, 1]))
print(coin_change_MULTI(1, [2,4,6,12,7,3,1]))
print(coin_change_MULTI(1, [2,4,6,12,7,3]))
print(coin_change_MULTI(100, [2,4,6,12,7,3,1]))
print(coin_change_MULTI(576, [2,4,6,12,7,3,1]))
print(coin_change_MULTI(12096, [2,4,6,12,7,3,1]))
print(coin_change_MULTI(0, [2,4,6,12,7,3,1]))
print((coin_change_MULTI(24, [2,4,6,12,7,3,1])))

[[1, 2, 6], [1, 3, 4], [1, 12], [2, 6], [3, 4], [12]]
[[1]]
[]
[]
[[1, 2, 4, 6, 12], [2, 4, 6, 12]]
[[1, 2, 3, 4, 6, 7, 12], [2, 3, 4, 6, 7, 12]]
[]
[[1, 2, 3, 4], [1, 2, 12], [1, 4, 6], [2, 3, 4], [2, 12], [4, 6]]
``````

Process finished with exit code 0