סובסעט סאַם לעעטקאָדע


שוועריקייט לעוועל מיטל
מענגע דינאַמיש פּראָגראַממינג

סובסעט סומע לעעטקאָדע פּראָבלעם שטאַטן אַז געגעבן אַן מענגע אַ [] פון גרייס ען. קאָנטראָלירן צי די מענגע קענען זיין צעטיילט אין צוויי סובסעץ אַזוי אַז די סומע פון ​​וואַלועס פון איין סאַבסעט איז גלייַך צו די אנדערע סאַבסעט. דרוקן "יאָ" אויב עס איז מעגלעך אַנדערש "ניין".

בייַשפּיל

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

דערקלערונג: די סומע פון ​​דער ערשטער און רגע עלעמענטן יקוואַלז די דריט עלעמענט. אזוי, דער געגעבן מענגע קענען זיין צעטיילט אין צוויי סובסעץ.

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

דערקלערונג: עס איז ניט מעגלעך קאָמבינאַציע אַזוי אַז די מענגע קענען זיין צעטיילט אין צוויי סובסעץ, אַזוי אַז זיי האָבן די זעלבע סומע.

רעקורסיווע מעטאָד

אַלגאָריטהם

1. יניטיאַליזירן אַ מענגע a [] פון גרייס n.
2. דורך די מענגע און געפֿינען די סומע פון ​​אַלע עלעמענטן אין די געגעבן מענגע אַ []. טשעק אויב סומע מאָד 2 איז ניט 0, ווייַזן פאַלש.
3. שאַפֿן אַ פונקציאָנירן אַז טשעקס אויב עס איז קיין סאַבסעט אין אַ מענגע וועמענס סאַכאַקל איז גלייַך צו האַלב פון די סומע פון ​​די פול אָריגינעל מענגע.
4. רוף דעם פֿונקציע רעקורסיוועלי דורך ינקלוסיוו די לעצטע עלעמענט און דורך עקסקלודינג די לעצטע עלעמענט.
5. אויב די סומע איז נול, צוריקקומען אמת. אַנדערש אויב די סומע איז נישט נול און n איז נול, קערט פאַלש.

ימפּלעמענטאַטיאָן פֿאַר סובסעט סאַם לעעטקאָדע

C ++ קאָד פֿאַר סובסעט סאַם

#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

Java קאוד פֿאַר סובסעט סאַם

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

קאַמפּלעקסיטי אַנאַליסיס פֿאַר סובסעט סאַם לעעטקאָדע

צייט קאַמפּלעקסיטי

זינט יעדער פּראָבלעם איז צעטיילט אין צוויי סמאָלער סאַב-פּראָבלעמס. אַז אַלגערידאַם האט אָ (2n) צייט קאַמפּלעקסיטי, ווו n איז די נומער פון ינטאַדזשערז אין די געגעבן מענגע אַ [].

ספעיס קאַמפּלעקסיטי

אָ (1) ווייַל מיר געוויינט קעסיידערדיק עקסטרע פּלאַץ.

דינאַמיש פּראָגראַממינג מעטאַד

אַלגאָריטהם

1. יניטיאַליזירן אַ מענגע a [] פון גרייס n.
2. דורך די מענגע און געפֿינען די סומע פון ​​אַלע עלעמענטן. טשעק אויב סומע מאָד 2 איז ניט 0, ווייַזן פאַלש.
3. שאַפֿן אַ 2 ד מענגע.
4. דערהייַנטיקן די ערשטער רודערן ווי אמת און דער ערשטער זייַל פון יעדער רודערן ווי פאַלש.
5. אָנהייב טראַווערסינג און דערהייַנטיקן דעם טייל [] [] ווי אמת אויב די סומע פון ​​קיין סאַבסעט פון דער אָריגינעל מענגע ביז דזש -1 איז גלייַך צו i. אלזא פאלש.
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

Java קאָד פֿאַר סובסעט סאַם

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) וווּ n איז די נומער פון גאַנץ נומערן אין די געגעבן מענגע אַ [] און די סומע איז די סומע פון ​​אַלע די עלעמענטן אין דער געגעבן מענגע אַ [].

ספעיס קאַמפּלעקסיטי

אָ (סומע * n) ווייַל מיר געוויינט סומע * n עקסטרע פּלאַץ.

רעפֿערענצן