સબસેટ સર લીટકોડ


મુશ્કેલી સ્તર મધ્યમ
અરે ડાયનેમિક પ્રોગ્રામિંગ

સબસેટ સરવાળા લીટકોડ સમસ્યા જણાવે છે કે એક એરે a [] કદ n. એરેને બે સબસેટમાં વહેંચી શકાય કે કેમ તે તપાસો કે એક સબસેટના મૂલ્યોનો સરવાળો અન્ય સબસેટની સમાન છે. “હા” છાપી જો શક્ય હોય તો “ના”.

ઉદાહરણ

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

સમજૂતી: પ્રથમ અને બીજા તત્વોનો સરવાળો ત્રીજા તત્વની બરાબર છે. આમ, આપેલ એરેને બે પેટામાં વહેંચી શકાય છે.

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

સમજૂતી: ત્યાં કોઈ સંભવિત સંયોજન નથી કે એરેને બે પેટામાં વહેંચી શકાય, જેમ કે તેમની સમાન રકમ છે.

પુનરાવર્તિત પદ્ધતિ

અલ્ગોરિધમ

1. કદ n ની એરે a [] ને પ્રારંભ કરો.
2. એરેને પસાર કરો અને આપેલા એરે એ [] માંના બધા ઘટકોનો સરવાળો શોધો. સરવાળા મોડ 2 ન 0 છે કે નહીં તે તપાસો, ખોટા પાછા ફરો.
3. બનાવો કાર્ય જે તપાસે છે કે અરેમાં કોઈ સબસેટ છે કે જેનો સરવાળો સંપૂર્ણ મૂળ એરેના અડધા સરવાળા જેટલો છે.
This. છેલ્લા ઘટકનો સમાવેશ કરીને અને છેલ્લા ઘટકને બાકાત રાખીને આ કાર્યને વારંવાર ક Callલ કરો.
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

સબસેટ સમ લીટકોડ માટે જટિલતા વિશ્લેષણ

સમય જટિલતા

કારણ કે દરેક સમસ્યાને બે નાના પેટાપ્રૂબલ્સમાં વહેંચવામાં આવી રહી છે. તે છે અલ્ગોરિધમનો પાસે ઓ (2) છેn) સમય જટિલતા, જ્યાં આપેલ એરેમાં પૂર્ણાંકોની સંખ્યા એ [] છે.

અવકાશ જટિલતા

ઓ (1), કારણ કે અમે સતત વધારાની જગ્યાનો ઉપયોગ કર્યો છે.

ગતિશીલ પ્રોગ્રામિંગ પદ્ધતિ

અલ્ગોરિધમ

1. કદ n ની એરે a [] પ્રારંભ કરો.
2. એરેને પસાર કરો અને બધા તત્વોનો સરવાળો શોધો. સરવાળા મોડ 2 ન 0 છે કે નહીં તે તપાસો, ખોટા પાછા ફરો.
3. 2D એરે બનાવો.
True. પ્રથમ પંક્તિને સાચું અને દરેક પંક્તિની પહેલી કોલમને ખોટી તરીકે અપડેટ કરો.
Tra. જાવ-5 સુધી મૂળ એરેના કોઈપણ સબસેટનો સરવાળો i ની બરાબર હોય તો ટ્ર traવર્સિંગ અને ભાગને અપડેટ કરો [] [] સાચું તરીકે બાકી ખોટું.
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

સબસેટ સમ લીટકોડ માટે જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (સરવાળો * એન) જ્યાં n આપેલ એરે એમાં પૂર્ણાંકોની સંખ્યા છે []] અને સરવાળો આપેલ એરે એના તમામ ઘટકોનો સરવાળો એ છે [].

અવકાશ જટિલતા

ઓ (સરવાળો * એન) કારણ કે અમે રકમ * એન વધારાની જગ્યાનો ઉપયોગ કર્યો છે.

સંદર્ભ