This is definitely an overkill, but since I've been using this method in my research recently, I hope this inspires some other fancy ideas.
Let n = len(coins)
Let x = [x0, x1, x2, ..., xn - 1] such that x * coins + x * coins + ... + x[n - 1] * coins[n - 1] = amount
We can then form the integer linear programming as:
x * coins + x * coins + ... + x[n] * coins[n - 1] = amount
x[i] > 0 x[i] is integer
with the help of python optimization package cvxopt (convex optimization) and glpk (GNU Linear Programming Kit), a relatively concise piece of code can be done.
Equality constraint are formed as matrices G and h, inequality constraint are formed as matrices A and b, c is the coefficients of objective function, in this case, is a all-one 1-d matrix
class Solution(object): def coinChange(self, coins, amount): """ :type coins: List[int] :type amount: int :rtype: int """ if amount == 0: return 0 if coins == : return -1 import numpy as np from cvxopt import matrix from cvxopt.glpk import ilp c = np.ones(len(coins)) A = np.array([coins]) b = np.array([amount]) G = np.diag(-1 * np.ones(len(coins))) h = np.zeros(len(coins)) intVars = set(range(len(coins))) status, isol = ilp(c = matrix(c.astype(float)), G = matrix(G.astype(float)), h = matrix(h.astype(float)), A = matrix(A.astype(float)), b = matrix(b.astype(float)), I = intVars) return int(sum(isol)) if status == 'optimal' else -1
Additionally, If return isol instead of sum(isol), you can get the exact combination of those coins
This uses something like branch and bound method hence a optimal solution is guaranteed if exists, but it also has a O(N^K) worst case complexity, where N is the size of coins and K is the upper bound of x[i], which can be estimated by amount / min(coins), my memory can be corrupted so don't rely on my words about details
If you really care about details or having an insomnia, here are some more dry readings