पायथन में जांचें कि क्या हम दो पार्टीशन का ग्रुप बना सकते हैं जिनका योग समान हो

मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है, हमें जांचना है कि क्या हम nums को दो ग्रुप में पार्टीशन कर सकते हैं जहां दोनों ग्रुप में तत्वों का योग समान हो।

उदाहरण के लिए, यदि इनपुट nums = [2, 3, 6, 5] है, तो आउटपुट True होगा, क्योंकि हम [2, 6] और [3, 5] जैसे ग्रुप बना सकते हैं।

इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे

• total := nums में सभी तत्वों का योग
• यदि total विषम है, तो
  • False लौटाएं
• half := total / 2 का पूर्णांक भाग
• dp := half + 1 आकार की एक सूची और false से भरें
• dp[0] := true
• nums में प्रत्येक num के लिए, करें
  • i को half से 0 तक, 1 से घटाकर रेंज में, करें
    • यदि i >= num, तो
      • dp[i] := dp[i] OR dp[i - num]
• dp[half] लौटाएं

उदाहरण

class Solution:    def solve(self, nums):       total = sum(nums)       if total & 1:          return False       half = total // 2       dp = [True] + [False] * half       for num in nums:          for i in range(half, 0, -1):             if i >= num:                dp[i] |= dp[i - num]       return dp[half] ob = Solution() nums = [2, 3, 6, 5] print(ob.solve(nums))

इनपुट

[2, 3, 6, 5]

आउटपुट

True