Python में दिए गए तत्वों के समुच्चय से दिए गए योग प्राप्त करने की संभावना की जांच कैसे करें?

मान लीजिए हमारे पास nums नामक एक सरणी है और एक अन्य मान sum है। हमें यह जांचना है कि क्या nums में मौजूद तत्वों को जोड़कर sum प्राप्त करना संभव है, हम एक तत्व को कई बार चुन सकते हैं।

तो, यदि इनपुट nums = [2, 3, 5], sum = 28 है, तो आउटपुट True होगा क्योंकि हम 5 + 5 + 5 + 5 + 3 + 3 + 2 का उपयोग करके 26 प्राप्त कर सकते हैं।

हल करने के चरण

• MAX := 1000
• table := आकार MAX की सरणी और 0 से भरें
• util() फ़ंक्शन परिभाषित करें। यह nums लेगा
• table[0] := 1
• nums सूची को क्रमबद्ध करें
• रेंज 0 से nums के आकार - 1 तक के लिए i, करें:
  • val := nums[i]
  • यदि table[val] शून्येतर है, तो:
    • अगले पुनरावृत्ति के लिए जाएं
  • रेंज 0 से MAX - val - 1 तक के लिए j, करें:
    • यदि table[j] शून्येतर है, तो:
      • table[j + val] := 1
• मुख्य विधि से निम्नलिखित करें:
  • util(nums)
  • यदि table[sum] शून्येतर है, तो:
    • True लौटाएं
  • False लौटाएं

उदाहरण

MAX = 1000
table = [0] * MAX

def util(nums):
    table[0] = 1
    nums.sort()
    for i in range(len(nums)):
        val = nums[i]
        if table[val]:
            continue
        for j in range(MAX - val):
            if table[j]:
                table[j + val] = 1

def solve(nums, sum):
    util(nums)
    if table[sum]:
        return True
    return False

nums = [2, 3, 5]
sum = 28
print(solve(nums, sum))

इनपुट

[2, 3, 5], 28

आउटपुट

True