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

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.

CodePudding user response：

Maybe you should combine

if lst[0] > 1: 
else:

together, that means for 1 we should also decide whether take it or not.

CodePudding user response：

Here is a simple workaround that requires very little change:

coins = [1,2,3,4,5]
combinations = Coin(20, coins, [], [])
print(combinations)
if 1 in coins:
    for combination in combinations:
        if 1 in combination:
            combinations.append([coin for coin in combination if coin != 1])
print(combinations)
# prints [[1, 2, 2, 5], [1, 4, 5], [2, 2, 5], [4, 5]]

You could simply remove 1 from each combination where it occurs, and add the new combination to the result.

CodePudding user response：

This is much easier to do with a generator using yield than a function using return.

The difference is that you can only return once, while you can yield any number of times (including 0 if there are no solutions).

If you wish to return a list, you still can, like this:

def coin (target, lst):
    return list(_coin(target, lst, 0)

def _coin (target, lst, i):
    ...

If that doesn't matter, the generator saves memory by not having to generate the whole list at once. And you simply:

def coin (target, lst, i=0):
    ... # Use yield as often as you want, all will be returned.

Second, you are running into the most common gotcha in Python. You are using mutable objects as defaults. If you're going to continue with your current approach you need to:

def coin(target, lst, temp=None, comb=None):
    if temp is None:
        temp = []
    if comb is None:
        comb = []
    ...

And third, you should get in the habit of following standard style conventions. In many ways, what the convention is doesn't matter that much. But that everyone is on the same page, does. Therefore you should try to follow the most common Python convention. In which the function should be named coin instead of Coin.