Fix coin change brute force solution

user_4787354 0
Viewed 1689

I am starting to write and understand coin change problem and couldn't get intuition so I have started to write a brute force solution. I want to understand the brute force solution before moving to memoization. 

coins = [2, 3, 7]
change = 12

def coin_change(c):
    print(c)
    if c <= 0:
        return 0
    else:
        for i in coins:
            if c - i >= 0:
                coin_change(c - i)

coin_change(change)

It prints out couple of changes left but I don't know how to store each path in an array.

I also want to understand how recursion can be used to track path. I can think of adding an extra argument in coin_change but maybe there is an alternate way.

I am confused about its complexity. It has a number of coins call at every step but many online resources mention it's 2n.

Edit: Please note that the coin supply is unlimited, The answer is 4

[2, 2, 2, 2, 2, 2]
[3, 3, 3, 3]
[2, 2, 2, 3, 3]
[2, 3, 7]
recursion python
3 Answers

Understanding the coin change problem:

Assuming you're referring to the problem of calculating change with the least number of coins, the key idea here is to think of the problem as making a choice at each step - which in this case is 'what coin to dispense next?'

You can break down the problem as coin_change(score) = 1 + min{coin_change(score - c1), coin_change(score - c2), ...} where c1, c2... are the coins you have.

Tracking the pathways:

This is fairly straightforward. Instead of returning the solution (minimum coin combination), simply return all possibilities (all coin combinations). So when you make the recursive call for (score-c1) say, then you get all combinations of coins that make (score-c1) and you just add c1 to them.

The code

coins = [2, 3, 7]
change = 12

def coin_change(c):
  if c == 0:
    return [[]]     # the only combo possible is no coins
  if c < 0:
    return []      # no combos possible
  else:
    all_combos = []
    for i in coins:
      recursive_result = coin_change(c-i)
      for combo in recursive_result:
        combo.append(i)
      all_combos.extend(recursive_result)

    return all_combos

result = coin_change(change)
for combo in result:
  print(combo)

Note: this will give you all permutations. If order doesn't matter, you can use sets to remove duplicates

Edit: Following comments, here's the code that removes duplicates

coins = [2, 3, 7]
change = 12

def removeDuplicates(combos):
  filtered = set()
  for combo in combos:
    combo.sort()
    filtered.add(tuple(combo))
  return [list(i) for i in filtered]

def coin_change(c):
  if c == 0:
    return [[]]     # the only combo possible is no coins
  if c < 0:
    return []      # no combos possible
  else:
    all_combos = []
    for i in coins:
      recursive_result = coin_change(c-i)
      for combo in recursive_result:
        combo.append(i)
      all_combos.extend(recursive_result)

    return removeDuplicates(all_combos)

result = coin_change(change)
for combo in result:
  print(combo)
user_135976750

Here is an example to get all paths for the coins. In general, when you write a recursive function, you want to 1) have a condition that exits the recursion, and 2) write how to extend the previous recursive step. 

coins  = [2, 3, 7]
change = 12

def coin_change_paths(paths):
    if all(sum(path)>=change for path in paths):
        return paths
    new_paths = []
    for path in paths:
        if sum(path)<change:
            new_paths.extend(path+[c] for c in coins)
        else:
            new_paths.append(path)
    return coin_change_paths(new_paths)

paths = coin_change_paths([[2],[3],[7]])

This doesn't account for duplication. To do that you should sort and then dedup: 

paths = [sorted(p) for p in paths]
temp = []
for p in paths:
    if p not in temp:
        temp.append(p)
paths = temp

You still have to check which ones are valid. 

paths = [p for p in paths if sum(p)==change]
print(paths)

Try to see if you can combine these together and simplify the code.

user_133952300

Another possible approach is to use a recursive generator function with yield and yield from. This removes the need to save the discovered combinations in a list, which then has to be returned:

coins = [2, 3, 7]
change = 12
def coin_change(c = []):
  if sum(c) == change:
     yield tuple(sorted(c))
  else:
     for i in coins:
        if sum(c+[i]) <= change:
           yield from coin_change(c+[i])

print(list(map(list, set(coin_change()))))

Output:

[[3, 3, 3, 3], [2, 2, 2, 3, 3], [2, 3, 7], [2, 2, 2, 2, 2, 2]]
user_73267380
Related