സബ്സെറ്റ് സം ലീറ്റ്കോഡ്


വൈഷമ്യ നില മീഡിയം
അറേ ഡൈനാമിക് പ്രോഗ്രാമിംഗ്

ഒരു നൽകിയ സബ്സെറ്റ് സം ലീറ്റ്കോഡ് പ്രശ്നം പറയുന്നു ശ്രേണി 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. ജെ -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 അധിക ഇടം ഉപയോഗിച്ചു.

അവലംബം