पायथन प्रोग्राम: सबसेट सम समस्या

इस लेख में हम दी गई समस्या के समाधान के बारे में जानेंगे।

समस्या कथन

हमें एक सरणी में गैर-ऋणात्मक पूर्णांकों का एक सेट दिया गया है, और एक मान sum दिया गया है, हमें यह निर्धारित करना है कि क्या दिए गए सेट का एक सबसेट मौजूद है जिसका योग दिए गए योग के बराबर है।

उदाहरण (साधारण दृष्टिकोण)

def SubsetSum(set, n, sum):
    # आधार मामले
    if (sum == 0):
        return True
    if (n == 0 and sum != 0):
        return False
    # यदि अंतिम तत्व sum से बड़ा है तो अनदेखा करें
    if (set[n - 1] > sum):
        return SubsetSum(set, n - 1, sum)
    # अन्यथा, योग जांचें
    # (1) अंतिम तत्व सहित
    # (2) अंतिम तत्व को छोड़कर
    return SubsetSum(set, n-1, sum) or SubsetSum(set, n-1, sum - set[n-1])

# मुख्य
set = [2, 14, 6, 22, 4, 8]
sum = 10
n = len(set)
if (SubsetSum(set, n, sum) == True):
    print("Found a subset with given sum")
else:
    print("No subset with given sum")

आउटपुट

Found a subset with given sum

उदाहरण (डायनामिक दृष्टिकोण)

# डायनामिक दृष्टिकोण
def isSubsetSum(set, n, sum):
    # DP टेबल
    dp = [[False for _ in range(sum + 1)] for _ in range(n + 1)]
    # sum 0 के लिए True
    for i in range(n + 1):
        dp[i][0] = True
    # टेबल भरें
    for i in range(1, n + 1):
        for j in range(1, sum + 1):
            if set[i-1] <= j:
                dp[i][j] = dp[i-1][j] or dp[i-1][j-set[i-1]]
            else:
                dp[i][j] = dp[i-1][j]
    return dp[n][sum]

# मुख्य
set = [2, 14, 6, 22, 4, 8]
sum = 10
n = len(set)
if isSubsetSum(set, n, sum):
    print("Found a subset with given sum")
else:
    print("No subset with given sum")

आउटपुट

Found a subset with given sum

निष्कर्ष

इस लेख में हमने सबसेट सम समस्या के पायथन प्रोग्राम के बारे में सीखा।