Data-Structures-and-Algorithms-Coursera/Algorithmic Tool Box/week6_dynamic_programming2/2_partitioning_souvenirs/partition3.cpp at master · Roopam-mishra/Data-Structures-and-Algorithms-Coursera · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
bool Possible(ll a[],ll subsetSum[],bool used[],ll sumofeachsubset,ll n,ll currIndex,ll lastindex)
{
    ll i,temp;
    bool next;
    if(subsetSum[currIndex]==sumofeachsubset)
    {
        if(currIndex==1)
            return true;
        return Possible(a,subsetSum,used,sumofeachsubset,n,currIndex+1,n-1);
    }
    for(i=lastindex;i>=0;i--)
    {
        if(used[i])
            continue;
        temp=subsetSum[currIndex]+a[i];
        if (temp<=sumofeachsubset)
        {
            used[i]=true;
            subsetSum[currIndex]+=a[i];
            next=Possible(a,subsetSum,used,sumofeachsubset,n,currIndex,i-1);
            used[i]=false;
            subsetSum[currIndex]-=a[i];
            if(next)
                return true;
        }
    }
    return false;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n,i,k,sum,sumofeachsubset;
    cin>>n;
    ll a[n],subsetSum[3];
    bool used[n];
    for(i=0;i<n;i++)
    cin>>a[i];
    if (n<3)
    {
        cout<<"0"<<endl;
        return 0;
    }
    sum=0;
    for (i=0;i<n;i++)
    sum+=a[i];
    if (sum%3!=0)
    {
        cout<<"0"<<endl;
        return 0;
    }
    sumofeachsubset=sum/3;
    for(i=0;i<3;i++)
    subsetSum[i]=0;
    for(i=0;i<n;i++)
    used[i]=false;
    subsetSum[0]=a[n-1];
    used[n-1]=true;
    if(Possible(a,subsetSum,used,sumofeachsubset,n,0,n-1))
        cout<<"1"<<endl;
    else
        cout<<"0"<<endl;
}