Complete search algorithm for combinations of coins
Don't gather all the combinations, just the sums.
Your set of sums starts with [0]. Cycle through the coins, one at a time. For each coin, iterate through its quantity, adding that multiple to each item of the set. Set-add each of these sums to the set. For example, let's take that original case: coins = [1, 2, 3], quant = [1, 2, 2]. Walking through this ...
sum_set = {0}
current_coin = 1; # coin[0]
current_quant = 1; # quant[0]
This step is trivial ... add 1 to each element of the set. This gives you {1}.
Add that to the existing set. You now have
sum_set = {0, 1}
Next coin:
current_coin = 2; # coin[0]
current_quant = 2; # quant[0]
Now, you have two items to add to each set element: 1*2, giving you {2, 3}; and 2*2, giving you {4, 5}.
Add these to the original set:
sum_set = {0, 1, 2, 3, 4, 5}
Final coin:
current_coin = 3; # coin[0]
current_quant = 2; # quant[0]
You add 1*3 and 2*3 to each set element, giving you {3, 4, 5, 6, 7, 8} and {6, 7, 8, 9, 10, 11}.
Adding these to the sum_set gives you the set of integers 0 through 11.
Remove 0 from the set (since we're not interested in that sum) and take the size of the remaining set. 11 is your answer.
Is that enough to let you turn this into an algorithm? I'll leave the various efficiencies up to you.
I was going to put up a solution using generating functions, but then you added
It is guaranteed that (quantity[0] + 1) * (quantity1 + 1) * ... * (quantity[quantity.length - 1] + 1) <= 10^6
In that case, just brute force it! Go through every possible set of coins, compute the sum, and use a set to find how many unique sums you get. 10^6 possibilities is trivial.
As for the generating function solution, we can represent the sums possible with a quantity Q of coins of value V through the polynomial
1 + x^V + x^(2V) + ... + x^(QV)
where a term with exponent N means a sum of value N can be achieved.
If we then multiply two polynomials, for example
(1 + x^(V1) + x^(2*V1) + ... + x^(Q1*V1))(1 + x^(V2) + x^(2*V2) + ... + x^(Q2*V2))
the presence of a term with exponent N in the product means that a sum of value N can be achieved by combining the coins corresponding to the input polynomials.
Efficiency then comes down to how we multiply polynomials. If we use dict
s or set
s to efficiently look up terms by exponent, we can win over brute force by combining like terms to eliminate some of the redundant work brute force does. We can discard the coefficients, since we don't need them. Advanced polynomial multiplication algorithms based on a number-theoretic transform may give further savings in some cases.
Bug fix
Your original solution is fine, except that you need to iterate in reverse order to avoid being able to keep adding the same coin multiple times.
Simply change the inner loop to:
for num in sorted(arr):
for i in range(len(dp)-1,-1,-1):
if num <= i:
dp[i] = dp[i] or dp[i - num]
More efficient solution
You can also reduce the complexity by taking advantage of the multiple coins with the same value by scanning up each possible remainder in turn:
def possibleSums2(coins, quantity):
maximum = sum((map(lambda t: t[0] * t[1], zip(coins, quantity))))
dp = [False] * (maximum + 1)
dp[0] = True
for coin,q in zip(coins,quantity):
for b in range(coin):
num = -1
for i in range(b,maximum+1,coin):
if dp[i]:
num = 0
elif num>=0:
num += 1
dp[i] = 0 <= num <= q
print(sum(dp) - 1)
This will have complexity O(maximum * coins) instead of O(maximum * coins * quantity)