Cp-Problems/Subset Sum.cpp at main · Malhotraankushgithub/Cp-Problems · 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

// approach 1
    vector<int> dp ;
    int total = 0 ;

    int partition ( int n , int arr[] , int sum )
    {
        if ( n < 0 )
        return 0 ;

        if ( dp[sum] != -1 )
        return dp[sum] ;

        if ( (sum * 2) == total )
        {
            return 1 ;
        }

        dp[sum] = partition ( n-1 , arr , sum + arr[n] ) || partition ( n-1 , arr , sum ) ;
        return dp[sum] ;
    }

    int equalPartition(int N, int arr[] )
    {
        // code here

        for ( int i=0 ; i < N ; i++ )
        {
            total += arr[i] ;
        }

        if ( total % 2 == 1 )
        return 0 ;

        dp.resize( total/2 + 1 , -1 );

        return partition ( N-1 , arr , 0 );
    }


// approach 2 - bitset

       int equalPartition(int N, int arr[])
    {  int sum=0;
        bitset<100001>dp;
        dp[0]=1;
        for(int i=0;i<N;i++){sum+=arr[i];dp|=(dp<<arr[i]);}
        if(sum%2)return 0;
        return dp[sum/2];
    }