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

Giả sử chúng ta có một danh sách các số phân biệt được gọi là num và một số khác k, chúng ta phải tìm số các tổ hợp phân biệt có tổng bằng k. Bạn có thể sử dụng lại các số khi tạo kết hợp.

Vì vậy, nếu đầu vào là nums =[2, 4, 5] k =4, thì đầu ra sẽ là 2, vì chúng ta có thể tạo hai nhóm như vậy như [2, 2] và [4].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:

• table:=một danh sách có kích thước k + 1 và điền bằng 0
• bảng [0]:=1
• đối với mỗi num trong nums, thực hiện
  • đối với tôi trong phạm vi num đến k, thực hiện
    • table [i]:=table [i] + table [i - num]
• bảng trả về [k]

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:

Mã mẫu

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