Підмножина Сума Leetcode


Рівень складності Medium
масив Динамічне програмування

Сума підмножини леет-коду говорить про те, що задано масив a [] розміром n. Перевірте, чи можна масив розділити на два підмножини так, щоб сума значень одного підмножини дорівнювала іншому підмножині. Роздрукуйте "Так", якщо можливо ще "Ні".

Приклад

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

Пояснення: Сума першого та другого елементів дорівнює третьому елементу. Таким чином, даний масив можна розділити на два підмножини.

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

Пояснення: Не існує такої можливої ​​комбінації, щоб масив можна було розділити на два підмножини, щоб вони мали однакову суму.

Рекурсивний метод

Алгоритм

1. Ініціалізуйте масив a [] розміром n.
2. Обведіть масив і знайдіть суму всіх елементів у даному масиві a []. Перевірте, якщо сума mod 2 не дорівнює 0, поверніть false.
3 Створити функція який перевіряє, чи є в масиві будь-яка підмножина, сума якої дорівнює половині суми повного вихідного масиву.
4. Викликати цю функцію рекурсивно, включаючи останній елемент і виключаючи останній елемент.
5. Якщо сума дорівнює нулю, поверніть true. В іншому випадку, якщо сума не дорівнює нулю і n дорівнює нулю, поверніть false.

Реалізація для підмножини Сума Leetcode

Код С ++ для суми підмножин

#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, поверніть false.
3. Створіть 2D-масив.
4. Оновіть перший рядок як true, а перший стовпець кожного рядка як false.
5. Почніть обхід та оновіть частину [] [] як істину, якщо сума будь-якого підмножини вихідного масиву до j-1 дорівнює i. В іншому випадку помилковий.
6. Повернути останнє булеве значення частково.

Реалізація для підмножини Сума Leetcode

Код С ++ для суми підмножин

#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) тому що ми використали додатковий пробіл sum * n.

посилання