సబ్‌సెట్ మొత్తం లీట్‌కోడ్


కఠినత స్థాయి మీడియం
అర్రే డైనమిక్ ప్రోగ్రామింగ్

సబ్‌సెట్ సమ్ లీట్‌కోడ్ సమస్య ఇచ్చినది అమరిక a [] పరిమాణం n. శ్రేణిని రెండు ఉపసమితులుగా విభజించవచ్చో లేదో తనిఖీ చేయండి, అంటే ఒక ఉపసమితి యొక్క విలువల మొత్తం ఇతర ఉపసమితికి సమానం. “అవును” అని ముద్రించండి.

ఉదాహరణ

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

వివరణ: మొదటి మరియు రెండవ మూలకాల మొత్తం మూడవ మూలకానికి సమానం. అందువలన, ఇచ్చిన శ్రేణిని రెండు ఉపసమితులుగా విభజించవచ్చు.

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

వివరణ: శ్రేణిని రెండు ఉపసమితులుగా విభజించగలిగే అవకాశం లేదు, అవి సమానమైన మొత్తాన్ని కలిగి ఉంటాయి.

పునరావృత పద్ధతి

అల్గారిథం

1. పరిమాణం n యొక్క [] శ్రేణిని ప్రారంభించండి.
2. శ్రేణిని దాటండి మరియు ఇచ్చిన శ్రేణిలోని అన్ని మూలకాల మొత్తాన్ని కనుగొనండి []. మొత్తం మోడ్ 2 0 కాదా అని తనిఖీ చేయండి, తప్పుడు తిరిగి ఇవ్వండి.
3. ఒక సృష్టించండి ఫంక్షన్ శ్రేణిలో ఏదైనా ఉపసమితి ఉందో లేదో తనిఖీ చేస్తుంది, దీని మొత్తం పూర్తి అసలు శ్రేణి యొక్క సగం మొత్తానికి సమానం.
4. చివరి మూలకాన్ని చేర్చడం ద్వారా మరియు చివరి మూలకాన్ని మినహాయించడం ద్వారా ఈ ఫంక్షన్‌ను పునరావృతంగా కాల్ చేయండి.
5. మొత్తం సున్నా అయితే, నిజం తిరిగి. లేకపోతే మొత్తం సున్నా కాకపోతే మరియు n సున్నా అయితే, తప్పుడు తిరిగి ఇవ్వండి.

సబ్‌సెట్ సమ్ లీట్‌కోడ్ కోసం అమలు

సబ్‌సెట్ మొత్తానికి సి ++ కోడ్

#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

సబ్‌సెట్ సమ్ లీట్‌కోడ్ కోసం సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

ప్రతి సమస్య రెండు చిన్న ఉప సమస్యలుగా విభజించబడుతోంది కాబట్టి. అల్గోరిథం O (2) కలిగి ఉందిn) సమయ సంక్లిష్టత, ఇక్కడ n అనేది ఇచ్చిన శ్రేణిలోని పూర్ణాంకాల సంఖ్య a [].

అంతరిక్ష సంక్లిష్టత

O (1), ఎందుకంటే మేము స్థిరమైన అదనపు స్థలాన్ని ఉపయోగించాము.

డైనమిక్ ప్రోగ్రామింగ్ విధానం

అల్గారిథం

1. పరిమాణం n యొక్క [] శ్రేణిని ప్రారంభించండి.
2. శ్రేణిని దాటండి మరియు అన్ని మూలకాల మొత్తాన్ని కనుగొనండి. మొత్తం మోడ్ 2 0 కాదా అని తనిఖీ చేయండి, తప్పుడు తిరిగి ఇవ్వండి.
3. 2 డి శ్రేణిని సృష్టించండి.
4. మొదటి అడ్డు వరుసను ఒప్పుగా మరియు ప్రతి అడ్డు వరుస యొక్క మొదటి నిలువు వరుసను తప్పుగా నవీకరించండి.
5. j-1 వరకు అసలు శ్రేణి యొక్క ఏదైనా ఉపసమితి మొత్తం i కి సమానంగా ఉంటే, ప్రయాణించడం ప్రారంభించండి మరియు భాగాన్ని [] [] నిజమని నవీకరించండి. వేరే తప్పుడు.
6. చివరి బూలియన్ విలువను కొంత భాగం తిరిగి ఇవ్వండి.

సబ్‌సెట్ సమ్ లీట్‌కోడ్ కోసం అమలు

సబ్‌సెట్ మొత్తానికి సి ++ కోడ్

#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 [] మరియు ఇచ్చిన శ్రేణిలోని అన్ని మూలకాల మొత్తం [].

అంతరిక్ష సంక్లిష్టత

O (మొత్తం * n) ఎందుకంటే మేము మొత్తం * n అదనపు స్థలాన్ని ఉపయోగించాము.

ప్రస్తావనలు