سبسیٹ سم لیٹکوڈ


مشکل سطح درمیانہ
لڑی متحرک پروگرامنگ

سبسیٹ سم لیٹ کوڈ مسئلہ میں بتایا گیا ہے کہ صف a [] سائز کا n. چیک کریں کہ آیا سرے کو دو ذیلی سیٹوں میں تقسیم کیا جاسکتا ہے جیسے ایک سبسیٹ کی اقدار کا مجموعہ دوسرے سب سیٹ کے برابر ہے۔ اگر ممکن ہو تو "نہیں" پرنٹ کریں۔

مثال کے طور پر

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

وضاحت: پہلے اور دوسرے عناصر کا مجموعہ تیسرے عنصر کے برابر ہے۔ اس طرح ، دیئے گئے سرے کو دو ذیلی ذیلیوں میں تقسیم کیا جاسکتا ہے۔

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

وضاحت: اس طرح کا کوئی امتزاج نہیں ہے کہ سرے کو دو ذیلی حصوں میں تقسیم کیا جاسکے ، جیسے کہ ان کا مساوی رقم ہو۔

تکرار کرنے کا طریقہ

الگورتھم

1. سائز این کی ایک صف کو ایک [] شروع کریں۔
2. صف کو عبور کریں اور دیئے گئے صف میں موجود تمام عناصر کا مجموعہ ڈھونڈیں a [] چیک کریں کہ اگر موڈ موڈ 2 0 نہیں ہے تو ، غلط کو واپس کریں۔
3. بنائیے ایک تقریب وہ چیک کرتا ہے کہ کیا کسی صف میں کوئی سب سیٹ موجود ہے جس کا مجموعہ مکمل اصل صف کے نصف کے برابر ہے۔
this. آخری عنصر کو شامل کرکے اور آخری عنصر کو چھوڑ کر اس فنکشن کو بار بار کال کریں۔
If. اگر رقم صفر ہے تو ، درست لوٹ آئیں۔ بصورت دیگر اگر رقم صفر نہیں ہے اور ن صفر ہے تو غلط کو لوٹائیں۔

سبسیٹ سم لیٹکوڈ کے لئے عمل درآمد

سب + سیٹ کے لئے 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

سب سیٹ کے لئے جاوا کوڈ

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) وقت کی پیچیدگی ، جہاں ن دیئے گئے صف میں ایک عددی کی تعداد ہے [a]۔

خلائی پیچیدگی

O (1) ، کیونکہ ہم مستقل اضافی جگہ استعمال کرتے ہیں۔

متحرک پروگرامنگ کا طریقہ

الگورتھم

1. سائز این کی ایک سرنی a [] کا آغاز کریں۔
2. صف کو عبور کریں اور تمام عناصر کا مجموعہ تلاش کریں۔ چیک کریں کہ اگر موڈ موڈ 2 0 نہیں ہے تو ، غلط کو واپس کریں۔
3. ایک 2D صف بنائیں۔
4. پہلی صف کو درست اور ہر صف کے پہلے کالم کو جھوٹا کے طور پر اپ ڈیٹ کریں۔
tra. ٹرانسورنگ شروع کریں اور اس حصے کو اپ ڈیٹ کریں [] [] سچ کے طور پر اگر جے -5 تک اصل صف کے کسی بھی سبسیٹ کا مجموعہ 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

سبسیٹ سم کے لئے جاوا کوڈ

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) کیونکہ ہم نے * n اضافی جگہ استعمال کی۔

حوالہ جات