Tìm số lượng tổng coin khác nhau từ coins và quantities trong Python

Cho list coins (giá trị) và quantities (số lượng tương ứng). Tìm số giá trị tổng khác nhau có thể tạo từ tập con không rỗng các coin.

Ví dụ: coins = [1,2,5], quantities = [1,2,1] → 10 tổng khác nhau: 1,2,3,4,5,6,7,8,9,10.

Giải pháp: Đệ quy backtracking. Với mỗi loại coin, thử lấy 0..quantity[i] cái, cộng dồn tổng, lưu vào set fres. Trừ đi 1 (tổng 0 từ tập rỗng).

Ví dụ triển khai

class Solution:
    def solve(self, coins, quantities):
        def rec(i, res):
            if i == len(coins):
                return
            for k in range(quantities[i] + 1):
                cur = res + k * coins[i]
                fres.add(cur)
                rec(i + 1, cur)
        fres = set()
        rec(0, 0)
        return len(fres) - 1

ob = Solution()
coins = [1, 2, 5]
quantities = [1, 2, 1]
print(ob.solve(coins, quantities))  # 10

Đầu vào

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

Đầu ra

10