BinarySearch 0630 Distinct Coin Sums

Problem statement

https://binarysearch.com/problems/Distinct-Coin-Sums/

Solution

Keep set of possible amounts and add coin by coin.

Complexity

If we have T = max(C), then we can have values upto T*n. We have time complexity O(T * n * m) and space is O(T * n).

Code

class Solution:
    def solve(self, C, Q):
        dp = set([0])
        for c, q in zip(C, Q):
            dp2 = set()
            for x in range(0, c*q + c, c):
                for val in dp:
                    dp2.add(x + val)
            dp = dp2
        return len(dp) - 1