Chương trình đếm số tổ hợp phân biệt có tổng bằng k trong Python

Mô tả bài toán

Cho danh sách các số khác nhau nums và số k. Đếm số tổ hợp phân biệt (có thể dùng lại số) có tổng bằng k.

Ví dụ: nums = [2, 4, 5], k = 4 → đầu ra 2 (tổ hợp [2,2] và [4]).

Giải thuật (Quy hoạch động - Coin Change)

1. Khởi tạo mảng table kích thước k+1 toàn 0, đặt table[0] = 1.
2. Với mỗi num trong nums:
   • Với i từ num đến k: table[i] += table[i - num].
3. Trả về table[k].

Ví dụ mã Python

class Solution:
    def solve(self, nums, k):
        table = [1] + [0] * k
        for num in nums:
            for i in range(num, k + 1):
                table[i] += table[i - num]
        return table[k]

ob = Solution()
nums = [2, 4, 5]
k = 4
print(ob.solve(nums, k))

Đầu vào

[2, 4, 5], 4

Đầu ra

2