सबसेट सम लेटकोड


कठिनाई स्तर मध्यम
ऐरे गतिशील प्रोग्रामिंग

सबसेट सम लेटकोड समस्या बताती है कि ए सरणी [a] आकार n। जांचें कि क्या सरणी को दो सबसेट में विभाजित किया जा सकता है जैसे कि एक सबसेट के मूल्यों का योग अन्य सबसेट के बराबर है। यदि संभव हो तो "हाँ" प्रिंट करें "नहीं"।

उदाहरण

a[ ] = {2, 3, 5}
Yes

स्पष्टीकरण: पहले और दूसरे तत्व का योग तीसरे तत्व के बराबर होता है। इस प्रकार, दिए गए सरणी को दो सबसेट में विभाजित किया जा सकता है।

a[ ] = {1, 2, 4, 9}
No

स्पष्टीकरण: ऐसा कोई संभावित संयोजन नहीं है कि सरणी को दो सबसेट में विभाजित किया जा सकता है, जैसे कि उनके पास समान राशि हो।

पुनरावर्ती विधि

कलन विधि

1. आकार n की एक सरणी [] को आरम्भ करें।
2. सरणी को ट्रैव करें और दिए गए सरणी [] में सभी तत्वों का योग ढूंढें। जाँच करें कि क्या राशि mod 2 0 नहीं है, तो गलत लौटें।
3। बनाओ समारोह यह जाँचता है कि किसी सरणी में कोई सबसेट है या नहीं जिसका योग पूर्ण मूल सरणी के आधे योग के बराबर है।
4. अंतिम तत्व को शामिल करके और अंतिम तत्व को छोड़कर इस फ़ंक्शन को पुन: कॉल करें।
5. यदि राशि शून्य है, तो सही लौटें। यदि योग शून्य नहीं है और शून्य शून्य है, तो गलत लौटें।

सबसेट सम लेटेकोड के लिए कार्यान्वयन

सी + + कोड सबसेट सम के लिए

#include <bits/stdc++.h> 
using namespace std; 
  
bool isEqualSum(int a[], int n, int sum){  
    if(sum == 0)  
        return true;  
    if(n == 0 && sum != 0)  
        return false;  
  
    if(a[n-1] > sum)  
       return isEqualSum(a, n-1, sum);  
  
    return isEqualSum(a, n-1, sum) ||  
        isEqualSum(a, n-1, sum-a[n-1]);  
}  
  
bool Partiion(int a[], int n){  
    int sum = 0;  
    for(int i=0; i<n; i++)  
    sum += a[i];  
  
    if(sum%2 != 0)  
        return false;  
  
    return isEqualSum (a, n, sum/2);  
}  
  
int main(){  
    int a[] = {2, 3, 5};  
    int n = sizeof(a)/sizeof(a[0]);  
    if(Partiion(a, n))  
        cout << "Yes";  
    else
        cout << "No";  
    return 0;  
}
Yes

सबसेट सम के लिए जावा कोड

import java.io.*; 
  
class equalSum{ 
    static boolean isEqualSum(int a[], int n, int sum){ 
        if(sum == 0) 
            return true; 
        if(n == 0 && sum != 0) 
            return false; 
  
        if(a[n-1] > sum) 
            return isEqualSum(a, n-1, sum); 
  
        return isEqualSum(a, n-1, sum) || 
               isEqualSum(a, n-1, sum-a[n-1]); 
    } 
  
    static boolean Partition (int a[], int n){ 
        int sum = 0; 
        for(int i = 0; i < n; i++) 
            sum += a[i]; 
  
        if (sum%2 != 0) 
            return false; 
  
        return isEqualSum(a, n, sum/2); 
    } 
  
    public static void main (String[] args){ 
  
        int a[] = {2, 3, 5}; 
        int n = a.length; 
        if(Partition(a, n) == true) 
            System.out.println("Yes"); 
        else
            System.out.println("No"); 
    } 
}
Yes

सबसेट सम लेटेकोड के लिए जटिलता विश्लेषण

समय जटिलता

चूंकि प्रत्येक समस्या को दो छोटे उपप्रकारों में विभाजित किया जा रहा है। यह है कि एल्गोरिथ्म में हे (2) हैn) समय जटिलता, जहां n दिए गए सरणी में पूर्णांक की संख्या है []।

अंतरिक्ष जटिलता

O (1), क्योंकि हमने निरंतर अतिरिक्त स्थान का उपयोग किया है।

गतिशील प्रोग्रामिंग विधि

कलन विधि

1. आरंभी एक सरणी [a] का आकार n।
2. सरणी को पार करें और सभी तत्वों का योग ढूंढें। जाँच करें कि क्या राशि mod 2 0 नहीं है, तो गलत लौटें।
3. एक 2 डी सरणी बनाएँ।
4. पहली पंक्ति को सत्य और प्रत्येक पंक्ति के पहले कॉलम को असत्य के रूप में अपडेट करें।
5. ट्रैवर्सिंग शुरू करें और भाग को अद्यतन करें [] [] उतना ही सच है यदि मूल सरणी के किसी भी सबसेट का योग j-1 तक बराबर है। और झूठे।
6. भाग में अंतिम बूलियन मान लौटाएं।

सबसेट सम लेटेकोड के लिए कार्यान्वयन

सबसेट सम के लिए C ++ कोड

#include <bits/stdc++.h> 
using namespace std; 
  
bool Partiion(int a[], int n){  
    int sum = 0; 
    int i, j; 

    for(i=0; i<n; i++) 
        sum += a[i]; 

    if(sum%2 != 0) 
        return false; 

    bool part[sum / 2 + 1][n + 1]; 

    for (i = 0; i <= n; i++) 
        part[0][i] = true; 

    for (i = 1; i <= sum/2; i++) 
        part[i][0] = false; 

    for(i=1; i<=sum/2; i++){ 
        for(j=1; j<=n; j++){ 
            part[i][j] = part[i][j-1]; 
            if(i >= a[j-1]) 
                part[i][j] = part[i][j] || 
                             part[i - a[j-1]][j-1]; 
        } 
    }
    return part[sum/2][n];   
}  
  
int main(){  
    int a[] = {2, 3, 5};  
    int n = sizeof(a)/sizeof(a[0]);  
    if(Partiion(a, n))  
        cout << "Yes";  
    else
        cout << "No";  
    return 0;  
}
Yes

सबसेट सम के लिए जावा कोड

import java.io.*; 
  
class equalSum{ 
    static boolean Partition (int a[], int n){ 
        int sum = 0; 
        int i, j; 
  
        for(i=0; i<n; i++) 
            sum += a[i]; 
  
        if(sum%2 != 0) 
            return false; 
  
        boolean part[][]=new boolean[sum/2+1][n+1]; 
  
        for (i = 0; i <= n; i++) 
            part[0][i] = true; 
  
        for (i = 1; i <= sum/2; i++) 
            part[i][0] = false; 
  
        for(i=1; i<=sum/2; i++){ 
            for(j=1; j<=n; j++){ 
                part[i][j] = part[i][j-1]; 
                if(i >= a[j-1]) 
                    part[i][j] = part[i][j] || 
                                 part[i - a[j-1]][j-1]; 
            } 
        }
        return part[sum/2][n];  
    } 
  
    public static void main (String[] args){ 
  
        int a[] = {2, 3, 5}; 
        int n = a.length; 
        if(Partition(a, n) == true) 
            System.out.println("Yes"); 
        else
            System.out.println("No"); 
    } 
}
Yes

सबसेट सम लेटेकोड के लिए जटिलता विश्लेषण

समय जटिलता

O (राशि * n) जहां n दिए गए एरे [a] में पूर्णांकों की संख्या है और योग दिए गए ए [a] में सभी तत्वों का योग है।

अंतरिक्ष जटिलता

O (राशि * n) क्योंकि हमने sum * n अतिरिक्त स्थान का उपयोग किया है।

संदर्भ