2

I am trying to get all the coins that are the sum of target amount. I was able to get the amount of coins needed. How would i go about solving it.

You can use the same coins unlimited eg. change([2], 10) => [2, 2, 2, 2, 2]

def change(coins, amount):
    result = [amount+1] * (amount+1)

    result[0] = 0

    for i in range(1, amount+1):
        for coin in coins:
            if i >= coin:
                result[i] = min(result[i], result[i-coin] + 1)

    if result[amount] == amount+1:
        return -1

    return result[amount]

change([1, 2, 5,8], 7) => [5, 2] order does not matter.

Community
  • 1
  • 1
mateo
  • 103
  • 1
  • 8
  • 1
    Please explain, in further detail, what you want to happen. –  Apr 13 '19 at 01:34
  • do you want all the result or the best result from dynamic programming? if you want all result, dynamic programming does not work here. – recnac Apr 13 '19 at 01:57

3 Answers3

6

If you use dyanmic programming you can only get the best result, you can achieve this by using a array to store the middle result of dynamic programming, I have modified based on your dp version:

def change(coins, amount):
    result = [amount+1] * (amount+1)
    coins_results = [[] for _ in range(amount+1)]

    result[0] = 0

    for i in range(1, amount+1):
        for coin in coins:
            if i >= coin and result[i - coin] + 1 < result[i]:
                result[i] = result[i-coin] + 1
                coins_results[i] = coins_results[i-coin] + [coin]

    if result[amount] == amount+1:
        return []

    return coins_results[amount]

test:

print(change([1, 2, 5, 8], 7))
print(change([2], 10))

output:

[5, 2]
[2, 2, 2, 2, 2]

here is a version to output all the result by backtracking:

def change(coins, amount):
    res = []

    def backtrack(end, remain, cur_result):
        if end < 0: return
        if remain == 0:
            res.append(cur_result)
            return
        if remain >= coins[end]:
            backtrack(end, remain - coins[end], cur_result + [coins[end]])
        backtrack(end - 1, remain, cur_result)

    backtrack(len(coins) - 1, amount, [])
    return res

test:

print(change([1, 2, 5, 8], 7))
print(change([2], 10))

output:

[[5, 2], [5, 1, 1], [2, 2, 2, 1], [2, 2, 1, 1, 1], [2, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1]]
[[2, 2, 2, 2, 2]]

Hope that helps you, and comment if you have further questions. : )

recnac
  • 3,744
  • 6
  • 24
  • 46
  • Thank you for you help, Its almost correct. when i used this testcase. print(change([51, 1], 10)) it returns [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] instead. – mateo Apr 13 '19 at 01:58
  • 1
    if you want all the result, I can write a different version, but dynamic programming can only get the best result @Don – recnac Apr 13 '19 at 01:59
  • im trying to solve that problems on LeetCode here is the link https://leetcode.com/problems/coin-change/ but i want to get it to return in a list. Id really appreciated your help. youre solid. – mateo Apr 13 '19 at 02:06
  • 1
    I think your code is the solution to this problem, if you want to get the specific result, you should edit your question here, because your desciption is `get all the coins that are the sum of target amount`, it is ambiguous : ) @Don – recnac Apr 13 '19 at 02:09
  • 1
    I have updated the version to output all the result, in case you needed. @Don – recnac Apr 13 '19 at 02:17
  • Yeah my description was wrong . Thank you for you help! – mateo Apr 13 '19 at 02:23
2

If you want to obtain all combinations that correspond to the target amount you can use the following generator:

def change(coins, amount):
    for i, coin in enumerate(coins):
        if coin == amount:
            yield (coin,)
        elif coin < amount:
            yield from ((coin,) + x for x in change(coins[i:], amount - coin))

print(list(change([2], 10)))  # [(2, 2, 2, 2, 2)]
print(list(change([1, 2, 5, 8], 7)))  # [(1, 1, 1, 1, 1, 1, 1), (1, 1, 1, 1, 1, 2), (1, 1, 1, 2, 2), (1, 1, 5), (1, 2, 2, 2), (2, 5)]
a_guest
  • 34,165
  • 12
  • 64
  • 118
1

I believe this is the answer you are looking for, please develop your question so we can get a better understanding of what is needed to be done :)

def change(coins, amount):
    ret = []    # Here we keep all possible solves
    solves = [] # Here we keep all unique solves, to avoid duplicates (Eg.: [5, 2] and [2, 5] are both a solution to 7)

    for c1 in coins:
        for c2 in coins:
            if c1 + c2 == amount: # Check if the solve is a match
                solve = [c1, c2] 
                if not set(solve) in solves: # Check if the solve is not a duplicate
                    ret.append(solve)
                    solves.append(set(solve))

    return ret # Return a list of solves
Pastre
  • 684
  • 8
  • 17