โปรแกรมนับชุดย่อยที่รวมกันเป็น k ใน python

สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums และอีกค่าหนึ่งคือ k เราต้องหาจำนวนชุดย่อยในรายการที่รวมกันได้ k หากคำตอบมีขนาดใหญ่มาก ให้แก้ไขด้วย 10^9 + 7

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[2, 3, 4, 5, 7] k =7 ผลลัพธ์จะเป็น 3 ดังที่เราสามารถเลือกเซตย่อย [2,5],[3,4] และ [ 7].

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

• dp :=รายการขนาด (k + 1) และเติมด้วย 0
• dp[0] :=1
• ม :=10^9 + 7
• สำหรับฉันในช่วง 0 ถึงขนาดของ nums - 1 ทำ
  • สำหรับ j ในช่วง k ลงไปที่ 0, ลดลง 1, ทำ
    • ถ้า nums[i] <=j แล้ว
      • dp[j] :=dp[j] + dp[j - nums[i]]
      • dp[j] :=dp[j] mod m

• คืนค่า dp[k] mod m

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

ตัวอย่าง

class Solution:
   def solve(self, nums, k):
      dp = [0] * (k + 1)
      dp[0] = 1
      m = int(1e9 + 7)
      for i in range(len(nums)):
         for j in range(k, -1, -1):
            if nums[i] <= j:
               dp[j] += dp[j - nums[i]]
               dp[j] %= m
      return dp[k] % m

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

อินพุต

[2, 3, 4, 5, 7], 7

ผลลัพธ์

3