โปรแกรมค้นหาจำนวนชุดค่าผสมที่แตกต่างกันซึ่งรวมกันเป็น k ใน python

สมมติว่าเรามีรายการตัวเลขที่แตกต่างกันซึ่งเรียกว่า nums และอีกจำนวนหนึ่งคือ k เราต้องหาจำนวนของชุดค่าผสมที่แตกต่างกันซึ่งรวมกันได้ k คุณสามารถใช้ตัวเลขซ้ำได้เมื่อสร้างชุดค่าผสม

ดังนั้น หากอินพุตเป็น nums =[2, 4, 5] k =4 เอาต์พุตจะเป็น 2 เนื่องจากเราสามารถสร้างกลุ่มดังกล่าวได้สองกลุ่ม เช่น [2, 2] และ [4]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:

• ตาราง :=รายการที่มีขนาด k + 1 และเติมด้วย 0
• ตาราง[0] :=1
• สำหรับแต่ละ num เป็น nums ทำ
  • สำหรับฉันอยู่ในช่วง num ถึง k ทำ
    • table[i] :=table[i] + table[i - num]
• กลับตาราง[k]

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:

โค้ดตัวอย่าง

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))

อินพุต

[2, 4, 5], 4

ผลลัพธ์

2