Υποσύνολο αθροίσματος Leetcode


Επίπεδο δυσκολίας Μέσον
Παράταξη Δυναμικός προγραμματισμός

Το πρόβλημα του υποσύνολου leetcode δηλώνει ότι δίνεται ένα παράταξη a [] μεγέθους n. Ελέγξτε εάν ο πίνακας μπορεί να χωριστεί σε δύο υποσύνολα έτσι ώστε το άθροισμα των τιμών ενός υποσυνόλου να είναι ίσο με το άλλο υποσύνολο. Εκτυπώστε «Ναι» αν είναι δυνατόν αλλιώς «Όχι».

Παράδειγμα

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

Επεξήγηση: Το άθροισμα του πρώτου και του δεύτερου στοιχείου ισούται με το τρίτο στοιχείο. Έτσι, ο δεδομένος πίνακας μπορεί να χωριστεί σε δύο υποσύνολα.

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

Επεξήγηση: Δεν υπάρχει πιθανός συνδυασμός έτσι ώστε ο πίνακας να χωρίζεται σε δύο υποσύνολα, έτσι ώστε να έχουν το ίδιο άθροισμα.

Αναδρομική μέθοδος

Αλγόριθμος

1. Αρχικοποιήστε έναν πίνακα a [] μεγέθους n.
2. Διασχίστε τον πίνακα και βρείτε το άθροισμα όλων των στοιχείων στον δεδομένο πίνακα a []. Ελέγξτε εάν το άθροισμα mod 2 δεν είναι 0, επιστρέψτε ψευδές.
3. Δημιουργώ ένα λειτουργία που ελέγχει εάν υπάρχει κάποιο υποσύνολο σε έναν πίνακα του οποίου το άθροισμα είναι ίσο με το μισό του αθροίσματος του πλήρους αρχικού πίνακα.
4. Καλέστε αυτήν τη λειτουργία αναδρομικά συμπεριλαμβάνοντας το τελευταίο στοιχείο και αποκλείοντας το τελευταίο στοιχείο.
5. Εάν το άθροισμα είναι μηδέν, επιστρέψτε το true. Διαφορετικά, εάν το άθροισμα δεν είναι μηδέν και το n είναι μηδέν, επιστρέψτε ψευδές.

Υλοποίηση για υποσύνολο αθροίσματος Leetcode

Κωδικός 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

Ανάλυση πολυπλοκότητας για υποσύνολο αθροίσματος Leetcode

Χρόνος πολυπλοκότητας

Δεδομένου ότι κάθε πρόβλημα χωρίζεται σε δύο μικρότερα υποπροβλήματα. Αυτός είναι ο αλγόριθμος που έχει O (2n) πολυπλοκότητα χρόνου, όπου n είναι ο αριθμός των ακεραίων στη δεδομένη συστοιχία a [].

Διαστημική πολυπλοκότητα

O (1), γιατί χρησιμοποιήσαμε σταθερό επιπλέον χώρο.

Μέθοδος δυναμικού προγραμματισμού

Αλγόριθμος

1. Αρχικοποιήστε έναν πίνακα a [] μεγέθους n.
2. Διασχίστε τον πίνακα και βρείτε το άθροισμα όλων των στοιχείων. Ελέγξτε εάν το άθροισμα mod 2 δεν είναι 0, επιστρέψτε ψευδές.
3. Δημιουργήστε έναν πίνακα 2D.
4. Ενημερώστε την πρώτη σειρά ως αληθινή και την πρώτη στήλη κάθε γραμμής ως ψευδής.
5. Ξεκινήστε να διασχίζετε και ενημερώστε το μέρος [] [] ως αληθές εάν το άθροισμα οποιουδήποτε υποσυνόλου του αρχικού πίνακα έως το j-1 είναι ίσο με το i. Άλλο ψεύτικο.
6. Επιστρέψτε εν μέρει την τελευταία τιμή boolean.

Υλοποίηση για υποσύνολο αθροίσματος Leetcode

Κωδικός 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

Ανάλυση πολυπλοκότητας για υποσύνολο αθροίσματος Leetcode

Χρόνος πολυπλοκότητας

O (άθροισμα * n) όπου n είναι ο αριθμός ακέραιων αριθμών στη δεδομένη συστοιχία a [] και το άθροισμα είναι το άθροισμα όλων των στοιχείων στη δεδομένη συστοιχία a [].

Διαστημική πολυπλοκότητα

O (άθροισμα * n) γιατί χρησιμοποιήσαμε άθροισμα * n επιπλέον χώρο.

αναφορές