โปรแกรมนับจำนวนการจัดหมู่ที่ผลรวมเท่ากับ k ใน Python

สมมติว่ามีรายการตัวเลขที่ไม่ซ้ำกัน nums และตัวเลข k ต้องการหาจำนวนการจัดหมู่ (combinations) ที่ผลรวมเท่ากับ k สามารถนำตัวเลขซ้ำใช้ได้

ตัวอย่าง: nums = [2, 4, 5], k = 4 ผลลัพธ์คือ 2 กลุ่มคือ [2, 2] และ [4]

ขั้นตอนการแก้ปัญหา

1. สร้าง table ขนาด k+1 เติม 0, ตั้ง table[0] = 1
2. วนลูปแต่ละ num ใน nums:
   • วน i จาก num ถึง k: table[i] += table[i - num]
3. คืนค่า table[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