पायथन में लक्ष्य प्राप्त करने के लिए प्रतीकों को व्यवस्थित करने के तरीकों की संख्या ढूंढने का प्रोग्राम

गैर-ऋणात्मक संख्याओं की सूची nums और पूर्णांक target दिया गया है। nums के प्रत्येक संख्या के सामने '+' या '-' चिह्न लगाकर व्यंजक का मूल्य target के बराबर करने के तरीकों की संख्या ढूंढें।

उदाहरण

इनपुट: nums = [2, 3, 3, 3, 2], target = 9

आउटपुट: 2

व्यंजक: -2 + 3 + 3 + 3 + 2 = 9 और 2 + 3 + 3 + 3 - 2 = 9।

मुख्य अंतर्दृष्टि (सबसेट योग में रूपांतरण)

मान लें P = धनात्मक चिह्न वाले संख्याओं का योग, N = ऋणात्मक चिह्न वाले संख्याओं का योग (पूर्ण मान)। तब:

P - N = target
P + N = sum(nums)
=> 2P = target + sum(nums)
=> P = (target + sum(nums)) / 2

इसलिए समस्या घटकर: nums का एक उपसमुच्चय ढूंढें जिसका योग P हो। तरीकों की संख्या = उपसमुच्चय योग की गिनती।

एल्गोरिदम (डायनामिक प्रोग्रामिंग)

1. s = sum(nums)।
2. यदि (s + target) % 2 != 0 या target > s: 0 वापस करें।
3. W = (s + target) // 2।
4. dp[0] = 1 (खाली उपसमुच्चय)।
5. प्रत्येक num in nums के लिए, W से num तक नीचे जाएं:
   • dp[j] += dp[j - num]
6. dp[W] वापस करें।

पायथन कार्यान्वयन

class Solution:
    def solve(self, nums, target):
        s = sum(nums)
        if (s + target) % 2 != 0 or target > s:
            return 0
        W = (s + target) // 2
        dp = [0] * (W + 1)
        dp[0] = 1
        
        for num in nums:
            for j in range(W, num - 1, -1):
                dp[j] += dp[j - num]
        return dp[W]

# परीक्षण
ob = Solution()
print(ob.solve([2, 3, 3, 3, 2], 9))  # 2
print(ob.solve([1, 1, 1, 1, 1], 3))  # 5

समय जटिलता

• O(n × W) जहां W = (sum + target)/2।
• स्थान: O(W)।

नोट

दिए गए कोड में दो DP सरणियों (dp1, dp2) का उपयोग किया गया है जो अनावश्यक है; मानक 1D DP पर्याप्त है। ऊपर दिया गया संस्करण सरल और कुशल है।