Equal Subset Sum | Leetcode | GFG

Statement - Given an array arr[] of size N, check if it can be partitioned into two parts such that the sum of elements in both parts is the same.

Example 1:

Input: N = 4
arr = {1, 5, 11, 5}
Output: YES
Explaination:  

The two parts are {1, 5, 5} and {11}. 

Question Link - Click

Code - using 1/0 knapsack.

class Solution{

public:

    bool f(int arr[], vector<vector<int>> &v, int n, int sum)

    {

        if(sum == 0) return true;

        if(sum < 0 || n < 0) return false;

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

        v[n][sum]  = f(arr, v, n - 1, sum) || f(arr, v, n - 1, sum - arr[n]) ? 1 : 0;

        return v[n][sum];  

    }

    int equalPartition(int n, int arr[])

    {

        // code here

        int sum = 0;

        for(int i = 0; i < n; i++)

        sum += arr[i];

        if(sum % 2 != 0) return 0;        

        sum /= 2; 

        vector<vector<int>> v(n+1, vector<int> (sum + 1, -1));   

        return f(arr, v, n-1, sum);

    }

};

Laptops For Coding