Ішкі жиынтық парағы


Күрделілік дәрежесі орта
Array Динамикалық бағдарламалау

Ішкі жиынның leetcode ақаулығы an бергенін айтады массив n [өлшемді a]]. Массивті екі ішкі жиынға бөлуге болатындығын тексеріңіз, сонда бір жиынның мәндерінің қосындысы екінші жиынға тең болады. Егер мүмкін болса, «Иә» басып шығарыңыз, «Жоқ».

мысал

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

Түсіндіру: Бірінші және екінші элементтердің қосындысы үшінші элементке тең. Сонымен, берілген жиымды екі ішкі жиынға бөлуге болады.

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

Түсіндіру: Массивті екі қосындыға бөлуге болатындай, мүмкін олардың қосындысы тең болатындай комбинация жоқ.

Рекурсивті әдіс

Алгоритм

1. n [өлшемді] массивті инициализациялаңыз.
2. Массивті айналып өтіп, берілген массивтегі барлық элементтердің қосындысын табыңыз []. Қосынды модулі 2-ге тең еместігін тексеріп, жалған мәнін қайтарыңыз.
3. Жасаңыз функция жиында толық жиымның қосындысының жартысына тең болатын жиынның бар-жоғын тексереді.
4. Бұл функцияны соңғы элементті қосу және соңғы элементті алып тастау арқылы рекурсивті түрде шақырыңыз.
5. Егер қосынды нөлге тең болса, шындық мәніне оралыңыз. Басқа жағдайда, егер қосынды нөлге тең емес, n нөлге тең болса, жалғанға қайтарыңыз.

Subet Sum 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

Subet Sum Leetcode жиынтығын талдау

Уақыттың күрделілігі

Әр мәселе екі кіші ішкі проблемаларға бөлінгендіктен. Алгоритмде O (2) барn) уақыттың күрделілігі, мұндағы n - берілген а [] жиымындағы бүтін сандардың саны.

Ғарыштың күрделілігі

O (1), өйткені біз тұрақты қосымша кеңістікті пайдаландық.

Динамикалық бағдарламалау әдісі

Алгоритм

1. n [өлшемді] массивті бастаңыз.
2. Массивті айналып өтіп, барлық элементтердің қосындысын табыңыз. Қосынды модулі 2-ге тең еместігін тексеріп, жалған мәнін қайтарыңыз.
3. 2D массивін құрыңыз.
4. Бірінші жолды шын, ал әрбір жолдың бірінші бағанын жалған етіп жаңартыңыз.
5. Қозғалысты бастаңыз және [] [] бөлігін шынайы етіп жаңартыңыз, егер бастапқы массивтің кез-келген ішкі жиыны j-1-ге дейін болса. Басқа жалған.
6. Соңғы логикалық мәнді ішінара қайтарыңыз.

Subet Sum 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

Subet Sum Leetcode жиынтығын талдау

Уақыттың күрделілігі

O (қосынды * n) Мұндағы n - берілген а [] жиымындағы бүтін сандардың саны, ал қосынды - берілген [[] жиымдағы барлық элементтердің қосындысы.

Ғарыштың күрделілігі

O (қосынды * n) өйткені біз * n қосымша орынды қолдандық.

Әдебиеттер тізімі