Partition equal subset sum

This question is a slight modification of the problem discussed in Subset-sum equal to target. We need to partition the array(say S) into two subsets(say S1 and S2). According to the question:

Sum of elements of S1 + sum of elements of S2 = sum of elements of S.
Sum of elements of S1 = sum of elements of S2.
These two conditions imply that S1 = S2 = (S/2).

Observation:

If S (sum of elements of the input array) is odd , there is no way we can divide it into two equal halves, so we can simply return false.
If S is even, then we need to find a subset in the input array whose sum is equal to S/2 because if we find one subset with sum S/2, the remaining elements sum will be automatically S/2. So, we can partition the given array. Hence we return true.

From here try to find a subset in the array with target = S/2 as discussed in Subset-sum equal to target.

The idea is to generate all pssible subsets and whenever a single subsets is found whose sum is equal to the given target(S/2), simply return true. As, all the subsets needs to generated, recursion can be used to solve this problem.

Steps to form the recursive solution:

Express the problem in terms of indexes: The array will have an index but there is one more parameter “target”. So, we can say that initially, we need to find(n-1, target) which means that we need to find whether there exists a subset in the array from index 0 to n-1, whose sum is equal to the target.

So, f(ind, target) will check whether a subset exists in the array from index 0 to index 'ind' such that the sum of elements is equal to the target.

Try out all possible choices at a given index: As all the subsets needs to be generated, we will use the pick/non-pick technique.There will be two choices in each function call:

Do not include the current element in the subset: First try to find a subset without considering the current index element. For this, make a recursive call to f(ind-1,target).

Include the current element in the subset: Now try to find a subset by considering the current index element as part of subset. As the current element(arr[ind]) is included, the remaining target sum will be target - arr[ind]. Therefore, make a function call of f(ind-1,target-arr[ind]).

Note: Consider the current element in the subset only when the current element is less or equal to the target.

/*It is pseudocode  and it is not tied to 
any specific programming  language*/

f(ind, target){
    not pick = f(ind-1, target)
    pick = false
    if(target <= arr[ind]{
        pick = f(ind-1, target - arr[ind])
    }
           
}

Return (pick || not pick): As we are looking for only one subset whose sum of elements is equal to target, if any of the one among 'pick' or 'not pick' returns true, it means the required subset is found so, return true.

/*It is pseudocode  and it is not tied to 
any specific programming  language*/

f(ind, target){
   not pick = f(ind-1, target)
    pick = false
    if(target <= arr[ind]{
        pick = f(ind-1, target - arr[ind])
    }
    return (pick || not pick)    
}

Base cases: There will be tow base cases, First, when target == 0, it means that the subset is already found from the previous steps, so simply return true. Another, when ind==0, it means we are at the first element, so return arr[ind]==target. If the element is equal to the target it will return true else false.

#include <bits/stdc++.h>
using namespace std;

class Solution{
private:
    /* Function to check if it's possible to partition
    the array into two subsets with equal sum*/
    bool func(int ind, int target, vector<int>& arr) {
        /* Base case: If the target sum is
        0, we found a valid partition*/
        if (target == 0)
            return true;

        /* Base case: If we have considered all elements 
        and the target is still not 0, return false*/
        if (ind == 0)
            return arr[0] == target;

        // Exclude the current element
        bool notTaken = func(ind - 1, target, arr);

        /* Include the current element if 
        it doesn't exceed the target*/
        bool taken = false;
        if (arr[ind] <= target)
            taken = func(ind - 1, target - arr[ind], arr);

        //Return the result
        return notTaken || taken;
    }
public:
    /* Function to check if the array can
    be partitioned into two equal subsets*/
    bool equalPartition(int n, vector<int>& arr) {
        int totSum = 0;

        // Calculate the total sum of the array
        for (int i = 0; i < n; i++) {
            totSum += arr[i];
        }

        /* If the total sum is odd, it cannot
        be partitioned into two equal subsets*/
        if (totSum % 2 == 1)
            return false;
            
        else{
            int k = totSum / 2;
            // Return the result
            return func(n - 1, k, arr);
        }
    }
};
int main() {
    vector<int> arr = {2, 3, 3, 3, 4, 5};
    int n = arr.size();
    
    //Create an instance of Solution class
    Solution sol;

    if (sol.equalPartition(n, arr))
        cout << "The Array can be partitioned into two equal subsets";
    else
        cout << "The Array cannot be partitioned into two equal subsets";

    return 0;
}
import java.util.*;

class Solution {
    /* Function to check if it's possible to partition 
    the array into two subsets with equal sum*/
    private boolean func(int ind, int target, int[] arr) {
        /* Base case: If the target sum is
        0, we found a valid partition*/
        if (target == 0)
            return true;

        /* Base case: If we have considered all elements 
        and the target is still not 0, return false*/
        if (ind == 0)
            return arr[0] == target;

        // Exclude the current element
        boolean notTaken = func(ind - 1, target, arr);

        /* Include the current element if
        it doesn't exceed the target*/
        boolean taken = false;
        if (arr[ind] <= target)
            taken = func(ind - 1, target - arr[ind], arr);

        // Return the result
        return notTaken || taken;
    }

    /* Function to check if the array can be
    partitioned into two equal subsets*/
    public boolean equalPartition(int n, int[] arr) {
        int totSum = 0;

        // Calculate the total sum of the array
        for (int i = 0; i < n; i++) {
            totSum += arr[i];
        }

        /* If the total sum is odd, it cannot be 
        partitioned into two equal subsets*/
        if (totSum % 2 == 1)
            return false;
        else {
            int k = totSum / 2;
            // Return the result
            return func(n - 1, k, arr);
        }
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 3, 3, 4, 5};
        int n = arr.length;

        // Create an instance of Solution class
        Solution sol = new Solution();

        if (sol.equalPartition(n, arr))
            System.out.println("The Array can be partitioned into two equal subsets");
        else
            System.out.println("The Array cannot be partitioned into two equal subsets");
    }
}
class Solution:
    """ Function to check if it's possible to partition 
    the array into two subsets with equal sum"""
    def func(self, ind, target, arr):
        """ Base case: If the target sum 
        is 0,we found a valid partition"""
        if target == 0:
            return True

        """ Base case: If we have considered all elements 
        and the target is still not 0, return false"""
        if ind == 0:
            return arr[0] == target

        # Exclude the current element
        not_taken = self.func(ind - 1, target, arr)

        """ Include the current element if
        it doesn't exceed the target"""
        taken = False
        if arr[ind] <= target:
            taken = self.func(ind - 1, target - arr[ind], arr)

        # Return the result
        return not_taken or taken

    """ Function to check if the array can be
    partitioned into two equal subsets"""
    def equalPartition(self, n, arr):
        tot_sum = 0

        # Calculate the total sum of the array
        for i in range(n):
            tot_sum += arr[i]

        """ If the total sum is odd, it cannot be 
        partitioned into two equal subsets"""
        if tot_sum % 2 == 1:
            return False
        else:
            k = tot_sum // 2
            # Return the result
            return self.func(n - 1, k, arr)

if __name__ == "__main__":
    arr = [2, 3, 3, 3, 4, 5]
    n = len(arr)

    # Create an instance of Solution class
    sol = Solution()

    if sol.equalPartition(n, arr):
        print("The Array can be partitioned into two equal subsets")
    else:
        print("The Array cannot be partitioned into two equal subsets")
class Solution {
    /* Function to check if it's possible to partition 
    the array into two subsets with equal sum*/
    func(ind, target, arr) {
        /* Base case: If the target sum 
        is 0, we found a valid partition*/
        if (target === 0) return true;

        /* Base case: If we have considered all elements
        and the target is still not 0, return false*/
        if (ind === 0) return arr[0] === target;

        // Exclude the current element
        const notTaken = this.func(ind - 1, target, arr);

        /* Include the current element if 
        it doesn't exceed the target*/
        let taken = false;
        if (arr[ind] <= target) {
            taken = this.func(ind - 1, target - arr[ind], arr);
        }

        // Return the result
        return notTaken || taken;
    }

    /* Function to check if the array can be 
    partitioned into two equal subsets*/
    equalPartition(n, arr) {
        let totSum = 0;

        // Calculate the total sum of the array
        for (let i = 0; i < n; i++) {
            totSum += arr[i];
        }

        /* If the total sum is odd, it cannot be
        partitioned into two equal subsets*/
        if (totSum % 2 === 1) return false;
        else {
            const k = totSum / 2;
            // Return the result
            return this.func(n - 1, k, arr);
        }
    }
}

const arr = [2, 3, 3, 3, 4, 5];
const n = arr.length;

// Create an instance of Solution class
const sol = new Solution();

if (sol.equalPartition(n, arr)) {
    console.log("The Array can be partitioned into two equal subsets");
} else {
    console.log("The Array cannot be partitioned into two equal subsets");
}

Time Complexity: O(2^(N)), where N is the length of the array. As, for each index, ther are two possible options.

Space Complexity:O(N), at maximum the depth of the recursive stack can go upto N.

If we draw the recursion tree, we will see that there are overlapping subproblems. Hence the DP approaches can be applied to the recursive solution.

In order to convert a recursive solution to memoization the following steps will be taken:

Declare a dp array of size [n][target+1]: As there are two changing parameters in the recursive solution, 'ind' and 'target'. The maximum value 'ind' can attain is (n), where n is the size of array and for 'target' only values between 0 to target. Therefore, we need 2D dp array.

The dp array stores the calculations of subproblems. Initialize dp array with -1, to indicate that no subproblem has been solved yet.

While encountering an overlapping subproblem: When we come across a subproblem, for which the dp array has value other than -1, it means we have found a subproblem which has been solved before hence it is an overlapping subproblem. No need to calculate it's value again just retrieve the value from dp array and return it.

Store the value of subproblem: Whenever, a subproblem is enocountered and it is not solved yet(the value at this index will be -1 in the dp array), store the calculated value of subproblem in the array.

#include <bits/stdc++.h>
using namespace std;

class Solution{
private:
    /* Function to check if it's possible to partition
    the array into two subsets with equal sum*/
    bool func(int ind, int target, vector<int> &arr, vector<vector<int>> &dp) {
        /* Base case: If the target sum is
        0, we found a valid partition*/
        if (target == 0)
            return true;

        /* Base case: If we have considered all elements 
        and the target is still not 0, return false*/
        if (ind == 0)
            return arr[0] == target;
        
        /* If the result for this state 
        is already calculated, return it*/
        if (dp[ind][target] != -1)
            return dp[ind][target];
            
        // Exclude the current element
        bool notTaken = func(ind - 1, target, arr, dp);

        /* Include the current element if 
        it doesn't exceed the target*/
        bool taken = false;
        if (arr[ind] <= target)
            taken = func(ind - 1, target - arr[ind], arr, dp);

        //Store the result and return it
        return dp[ind][target] = notTaken || taken;
    }
public:
    /* Function to check if the array can
    be partitioned into two equal subsets*/
    bool equalPartition(int n, vector<int>& arr) {
        int totSum = 0;

        // Calculate the total sum of the array
        for (int i = 0; i < n; i++) {
            totSum += arr[i];
        }

        /* If the total sum is odd, it cannot
        be partitioned into two equal subsets*/
        if (totSum % 2 == 1)
            return false;
            
        else{
            int k = totSum / 2;
            
            /* Initialize a DP table with dimensions
            n x k+1 and initialize with -1*/
            vector<vector<int>> dp(n, vector<int>(k + 1, -1));
            
            // Return the result
            return func(n - 1, k, arr, dp);
        }
    }
};
int main() {
    vector<int> arr = {2, 3, 3, 3, 4, 5};
    int n = arr.size();
    
    //Create an instance of Solution class
    Solution sol;

    if (sol.equalPartition(n, arr))
        cout << "The Array can be partitioned into two equal subsets";
    else
        cout << "The Array cannot be partitioned into two equal subsets";

    return 0;
}
import java.util.*;

class Solution {
    /* Function to check if it's possible to partition
    the array into two subsets with equal sum*/
    private boolean func(int ind, int target, int[] arr, int[][] dp) {
        /* Base case: If the target sum 
        is 0, we found a valid partition*/
        if (target == 0)
            return true;

        /* Base case: If we have considered all elements 
        and the target is still not 0, return false*/
        if (ind == 0)
            return arr[0] == target;

        /* If the result for this state is 
        already calculated, return it*/
        if (dp[ind][target] != -1)
            return dp[ind][target] == 1;

        // Exclude the current element
        boolean notTaken = func(ind - 1, target, arr, dp);

        /* Include the current element if
        it doesn't exceed the target*/
        boolean taken = false;
        if (arr[ind] <= target)
            taken = func(ind - 1, target - arr[ind], arr, dp);

        // Store the result and return it
        dp[ind][target] = (notTaken || taken) ? 1 : 0;
        return dp[ind][target] == 1;
    }

    /* Function to check if the array can 
    be partitioned into two equal subsets*/
    public boolean equalPartition(int n, int[] arr) {
        int totSum = 0;

        // Calculate the total sum of the array
        for (int i = 0; i < n; i++) {
            totSum += arr[i];
        }

        /* If the total sum is odd, it cannot be 
        partitioned into two equal subsets*/
        if (totSum % 2 == 1)
            return false;
        else {
            int k = totSum / 2;

            /* Initialize a DP table with dimensions
            n x k+1 and initialize with -1*/
            int[][] dp = new int[n][k + 1];
            for (int[] row : dp)
                Arrays.fill(row, -1);

            // Return the result
            return func(n - 1, k, arr, dp);
        }
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 3, 3, 4, 5};
        int n = arr.length;

        // Create an instance of Solution class
        Solution sol = new Solution();

        if (sol.equalPartition(n, arr))
            System.out.println("The Array can be partitioned into two equal subsets");
        else
            System.out.println("The Array cannot be partitioned into two equal subsets");
    }
}
class Solution:
    """ Function to check if it's possible to partition 
    the array into two subsets with equal sum"""
    def func(self, ind, target, arr, dp):
        """ Base case: If the target sum 
        is 0,we found a valid partition"""
        if target == 0:
            return True

        """ Base case: If we have considered all elements 
        and the target is still not 0, return false"""
        if ind == 0:
            return arr[0] == target
            
        """ If the result for this state 
        is already calculated, return it"""
        if dp[ind][target] != -1:
            return dp[ind][target] == 1

        # Exclude the current element
        not_taken = self.func(ind - 1, target, arr, dp)

        """ Include the current element if
        it doesn't exceed the target"""
        taken = False
        if arr[ind] <= target:
            taken = self.func(ind - 1, target - arr[ind], arr, dp)

        # Store the result and return it
        dp[ind][target] = 1 if not_taken or taken else 0
        return dp[ind][target] == 1

    """ Function to check if the array can be
    partitioned into two equal subsets"""
    def equalPartition(self, n, arr):
        tot_sum = 0

        # Calculate the total sum of the array
        for i in range(n):
            tot_sum += arr[i]

        """ If the total sum is odd, it cannot be 
        partitioned into two equal subsets"""
        if tot_sum % 2 == 1:
            return False
        else:
            k = tot_sum // 2
            
            """ Initialize a DP table with dimensions
            n x k+1 and initialize with -1"""
            dp = [[-1] * (k + 1) for _ in range(n)]
            
            # Return the result
            return self.func(n - 1, k, arr, dp)

if __name__ == "__main__":
    arr = [2, 3, 3, 3, 4, 5]
    n = len(arr)

    # Create an instance of Solution class
    sol = Solution()

    if sol.equalPartition(n, arr):
        print("The Array can be partitioned into two equal subsets")
    else:
        print("The Array cannot be partitioned into two equal subsets")
class Solution {
    /* Function to check if it's possible to partition 
    the array into two subsets with equal sum*/
    func(ind, target, arr, dp) {
        /* Base case: If the target sum 
        is 0, we found a valid partition*/
        if (target === 0) return true;

        /* Base case: If we have considered all elements
        and the target is still not 0, return false*/
        if (ind === 0) return arr[0] === target;
        
        /* If the result for this state 
        is already calculated, return it*/
        if (dp[ind][target] !== -1) return dp[ind][target] === 1;

        // Exclude the current element
        const notTaken = this.func(ind - 1, target, arr, dp);

        /* Include the current element if 
        it doesn't exceed the target*/
        let taken = false;
        if (arr[ind] <= target) {
            taken = this.func(ind - 1, target - arr[ind], arr, dp);
        }

        // Store the result and return it
        dp[ind][target] = (notTaken || taken) ? 1 : 0;
        return dp[ind][target] === 1;
    }

    /* Function to check if the array can be 
    partitioned into two equal subsets*/
    equalPartition(n, arr) {
        let totSum = 0;

        // Calculate the total sum of the array
        for (let i = 0; i < n; i++) {
            totSum += arr[i];
        }

        /* If the total sum is odd, it cannot be
        partitioned into two equal subsets*/
        if (totSum % 2 === 1) return false;
        else {
            const k = totSum / 2;
            
            /* Initialize a DP table with dimensions
            n x k+1 and initialize with -1*/
            const dp = Array.from({ length: n }, () => Array(k + 1).fill(-1));
            // Return the result
            return this.func(n - 1, k, arr, dp);
        }
    }
}

const arr = [2, 3, 3, 3, 4, 5];
const n = arr.length;

// Create an instance of Solution class
const sol = new Solution();

if (sol.equalPartition(n, arr)) {
    console.log("The Array can be partitioned into two equal subsets");
} else {
    console.log("The Array cannot be partitioned into two equal subsets");
}

Complexity Analysis:

Time Complexity: O(N*target), where target is the total sum of elements of the array divided by 2. There are 'N*target' states therefore at max ‘N*target’ new problems will be solved.

Space Complexity:O(N*target) + O(N), As we are using a recursion stack space(O(N)) and a 2D array ( O(N*target)).

In order to convert a recursive code to tabulation code, we try to convert the recursive code to tabulation and here are the steps:

Declare a dp array of size [n][target+1]: As there are two changing parameters in the recursive solution, 'ind' and 'target'. The maximum value 'ind' can attain is (n) and including 0 its n, where n is the size of array, for 'target' can have any values between 0 to 'target'. So we need a 2D dp array. Set its type as bool and initialize it as false.

Setting Base Cases in the Array: In the recursive code, our base condition was when target == 0, it means the required subset is found and we were returning true. So, set 'true' in the dp array for every index where target = 0.

The first row dp[0][] indicates that only the first element of the array is considered, therefore for the target value equal to arr[0], only cell with that target will be true, so explicitly set dp[0][arr[0]] =true, (dp[0][arr[0]] means that we are considering the first element of the array with the target equal to the first element itself). Please note that it can happen that arr[0]>target, so we first check it: if(arr[0]<=target) then set dp[0][arr[0]] = true.

Iterative Computation Using Loops: Initialize two nested for loops to traverse the dp array and following the logic discussed in the recursive approach, set the value of each cell in the 2D dp array. Instead of recursive calls, use the dp array itself to find the values of intermediate calculations.

Returning the answer: At last dp[n-1][target] will hold the solution after the completion of whole process, as we are doing the calculations in bottom-up manner.

#include <bits/stdc++.h>
using namespace std;

class Solution{
private:
    /* Function to check if it's possible to partition
    the array into two subsets with equal sum*/
    bool func(int ind, int target, int n, vector<int> &arr) {
        int totSum = 0;

        // Calculate the total sum of the array
        for (int i = 0; i < n; i++) {
            totSum += arr[i];
        }

        /* If the total sum is odd, it cannot
        be partitioned into two equal subsets*/
        if (totSum % 2 == 1)
            return false;
        else {
            int k = totSum / 2;

            /* Create a DP table with dimensions 
            n x k+1, initialized with false*/
            vector<vector<bool>> dp(n, vector<bool>(k + 1, false));

            /* Base case: If the target sum is 0, it 
            can be achieved by not selecting any elements*/
            for (int i = 0; i < n; i++) {
                dp[i][0] = true;
            }

            /* Initialize the first row based 
            on the first element of the array*/
            if (arr[0] <= k)
                dp[0][arr[0]] = true;

            // Fill in the DP table using bottom-up approach
            for (int ind = 1; ind < n; ind++) {
            
                for (int target = 1; target <= k; target++) {
                    // Exclude the current element
                    bool notTaken = dp[ind - 1][target];

                    /* Include the current element if
                    it doesn't exceed the target*/
                    bool taken = false;
                    if (arr[ind] <= target)
                        taken = dp[ind - 1][target - arr[ind]];

                    // Update the DP table
                    dp[ind][target] = notTaken || taken;
                }
            }
            /* The final result is in 
            the last cell of the DP table*/
            return dp[n - 1][k];
        }
    }
public:
    /* Function to check if the array can
    be partitioned into two equal subsets*/
    bool equalPartition(int n, vector<int>& arr) {
        int totSum = 0;

        // Calculate the total sum of the array
        for (int i = 0; i < n; i++) {
            totSum += arr[i];
        }

        /* If the total sum is odd, it cannot
        be partitioned into two equal subsets*/
        if (totSum % 2 == 1)
            return false;
            
        else{
            int k = totSum / 2;
            
            // Return the result
            return func(n - 1, k, n, arr);
        }
    }
};
int main() {
    vector<int> arr = {2, 3, 3, 3, 4, 5};
    int n = arr.size();
    
    //Create an instance of Solution class
    Solution sol;

    if (sol.equalPartition(n, arr))
        cout << "The Array can be partitioned into two equal subsets";
    else
        cout << "The Array cannot be partitioned into two equal subsets";

    return 0;
}
import java.util.*;

class Solution {
    /* Function to check if it's possible to partition
    the array into two subsets with equal sum*/
    private boolean func(int ind, int target, int n, int[] arr) {
        int totSum = 0;

        // Calculate the total sum of the array
        for (int i = 0; i < n; i++) {
            totSum += arr[i];
        }

        /* If the total sum is odd, it cannot 
        be partitioned into two equal subsets*/
        if (totSum % 2 == 1)
            return false;
        else {
            int k = totSum / 2;

            /* Create a DP table with dimensions
            n x k+1, initialized with false*/
            boolean[][] dp = new boolean[n][k + 1];

            /* Base case: If the target sum is 0, it can
            be achieved by not selecting any elements*/
            for (int i = 0; i < n; i++) {
                dp[i][0] = true;
            }

            /* Initialize the first row based 
            on the first element of the array*/
            if (arr[0] <= k)
                dp[0][arr[0]] = true;

            // Fill in the DP table using bottom-up approach
            for (int i = 1; i < n; i++) {
                
                for (int targetVal = 1; targetVal <= k; targetVal++) {
                    // Exclude the current element
                    boolean notTaken = dp[i - 1][targetVal];

                    /* Include the current element 
                    if it doesn't exceed the target*/
                    boolean taken = false;
                    if (arr[i] <= targetVal)
                        taken = dp[i - 1][targetVal - arr[i]];

                    // Update the DP table
                    dp[i][targetVal] = notTaken || taken;
                }
            }

            /* The final result is in the
            last cell of the DP table*/
            return dp[n - 1][k];
        }
    }

    /* Function to check if the array can 
    be partitioned into two equal subsets*/
    public boolean equalPartition(int n, int[] arr) {
        int totSum = 0;

        // Calculate the total sum of the array
        for (int i = 0; i < n; i++) {
            totSum += arr[i];
        }

        /* If the total sum is odd, it cannot 
        be partitioned into two equal subsets*/
        if (totSum % 2 == 1)
            return false;
        else {
            int k = totSum / 2;

            // Return the result
            return func(n - 1, k, n, arr);
        }
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 3, 3, 4, 5};
        int n = arr.length;

        // Create an instance of Solution class
        Solution sol = new Solution();

        if (sol.equalPartition(n, arr))
            System.out.println("The Array can be partitioned into two equal subsets");
        else
            System.out.println("The Array cannot be partitioned into two equal subsets");
    }
}
class Solution:
    """ Function to check if it's possible to partition
    the array into two subsets with equal sum"""
    def func(self, ind, target, n, arr):
        tot_sum = 0

        # Calculate the total sum of the array
        for i in range(n):
            tot_sum += arr[i]

        """ If the total sum is odd, it cannot 
        be partitioned into two equal subsets"""
        if tot_sum % 2 == 1:
            return False
        else:
            k = tot_sum // 2

            """ Create a DP table with dimensions
            n x k+1, initialized with False"""
            dp = [[False] * (k + 1) for _ in range(n)]

            """ Base case: If the target sum is 0, it can 
            be achieved by not selecting any elements"""
            for i in range(n):
                dp[i][0] = True

            """ Initialize the first row based 
            on the first element of the array"""
            if arr[0] <= k:
                dp[0][arr[0]] = True

            # Fill in the DP table using bottom-up approach
            for i in range(1, n):
                for target_val in range(1, k + 1):
                    # Exclude the current element
                    not_taken = dp[i - 1][target_val]

                    """ Include the current element 
                    if it doesn't exceed the target"""
                    taken = False
                    if arr[i] <= target_val:
                        taken = dp[i - 1][target_val - arr[i]]

                    # Update the DP table
                    dp[i][target_val] = not_taken or taken

            """ The final result is in the
            last cell of the DP table"""
            return dp[n - 1][k]

    """ Function to check if the array can 
    be partitioned into two equal subsets"""
    def equalPartition(self, n, arr):
        tot_sum = 0

        # Calculate the total sum of the array
        for i in range(n):
            tot_sum += arr[i]

        """ If the total sum is odd, it cannot 
        be partitioned into two equal subsets"""
        if tot_sum % 2 == 1:
            return False
        else:
            k = tot_sum // 2

            # Return the result
            return self.func(n - 1, k, n, arr)

if __name__ == "__main__":
    arr = [2, 3, 3, 3, 4, 5]
    n = len(arr)

    # Create an instance of Solution class
    sol = Solution()

    if sol.equalPartition(n, arr):
        print("The Array can be partitioned into two equal subsets")
    else:
        print("The Array cannot be partitioned into two equal subsets")
class Solution {
    /* Function to check if it's possible to partition
    the array into two subsets with equal sum*/
    func(ind, target, n, arr) {
        let totSum = 0;

        // Calculate the total sum of the array
        for (let i = 0; i < n; i++) {
            totSum += arr[i];
        }

        /* If the total sum is odd, it cannot be
        partitioned into two equal subsets*/
        if (totSum % 2 === 1)
            return false;
        else {
            const k = Math.floor(totSum / 2);

            /* Create a DP table with dimensions
            n x k+1, initialized with false*/
            const dp = Array.from({ length: n }, () => Array(k + 1).fill(false));

            /* Base case: If the target sum is 0, it can 
            be achieved by not selecting any elements*/
            for (let i = 0; i < n; i++) {
                dp[i][0] = true;
            }

            /* Initialize the first row based 
            on the first element of the array*/
            if (arr[0] <= k)
                dp[0][arr[0]] = true;

            // Fill in the DP table using bottom-up approach
            for (let i = 1; i < n; i++) {
                for (let targetVal = 1; targetVal <= k; targetVal++) {
                    // Exclude the current element
                    const notTaken = dp[i - 1][targetVal];

                    /* Include the current element 
                    if it doesn't exceed the target*/
                    let taken = false;
                    if (arr[i] <= targetVal)
                        taken = dp[i - 1][targetVal - arr[i]];

                    // Update the DP table
                    dp[i][targetVal] = notTaken || taken;
                }
            }

            /* The final result is in 
            the last cell of the DP table*/
            return dp[n - 1][k];
        }
    }

    /* Function to check if the array can 
    be partitioned into two equal subsets*/
    equalPartition(n, arr) {
        let totSum = 0;

        // Calculate the total sum of the array
        for (let i = 0; i < n; i++) {
            totSum += arr[i];
        }

        /* If the total sum is odd, it cannot 
        be partitioned into two equal subsets*/
        if (totSum % 2 === 1)
            return false;
        else {
            const k = Math.floor(totSum / 2);

            // Return the result
            return this.func(n - 1, k, n, arr);
        }
    }
}

const arr = [2, 3, 3, 3, 4, 5];
const n = arr.length;

// Create an instance of Solution class
const sol = new Solution();

if (sol.equalPartition(n, arr)) {
    console.log("The Array can be partitioned into two equal subsets");
} else {
    console.log("The Array cannot be partitioned into two equal subsets");
}

Complexity Analysis:

Time Complexity: O(N*target), where target is the total sum of elements of the array divided by 2. As, here are three nested loops that account for O(N*target) complexity.

Space Complexity:O(N*target), As a 2D array of size N*target is used.

If we closely look the relation, dp[ind][target] = dp[ind-1][target] || dp[ind-1][target-arr[ind]] We see that to calculate a value of a cell of the dp array, we need only the previous row values (say prev). So, we don’t need to store an entire array. Hence we can space optimize it.

Steps to space optimize the tabulation approach:

Decalre an array to store the previous row of the DP table. Initialize the first row and first column of the DP table based on the base conditions discussed in tabulation.
Now, initiate two nested loops in bottom-up approach. The first loop will run for 'ind' and the second loop will run for the 'target' variable.
In order to store the current row of the DP table, initialize a new array 'cur' and fill the first cell to 'true' for base condition.
Do the calculations for 'cur' row by performing the pick/non-pick technique used in previous approaches.
Now, update the previous row with the current row for the next iteration and at last return the final result stored in the last cell of the previous row(prev[k]).

#include <bits/stdc++.h>
using namespace std;

class Solution{
private:
    /* Function to check if it's possible to partition
    the array into two subsets with equal sum*/
    bool func(int n, vector<int> &arr) {
        int totSum = 0;

        // Calculate the total sum of the array
        for (int i = 0; i < n; i++) {
            totSum += arr[i];
        }

        /* If the total sum is odd, it cannot
        be partitioned into two equal subsets*/
        if (totSum % 2 == 1)
            return false;
        else {
            int k = totSum / 2;

            /* Create a vector to represent 
            the previous row of the DP table*/
            vector<bool> prev(k + 1, false);

            /* Base case: If the target sum is 0, it can
            be achieved by not selecting any elements*/
            prev[0] = true;

            /* Initialize the first row based 
            on the first element of the array*/
            if (arr[0] <= k)
                prev[arr[0]] = true;

            /* Fill in the DP table
            using a bottom-up approach*/
            for (int ind = 1; ind < n; ind++) {
                /* Initialize a vector to represent 
                the current row of the DP table*/
                vector<bool> cur(k + 1, false);
                cur[0] = true;

                for (int target = 1; target <= k; target++) {
                    // Exclude the current element
                    bool notTaken = prev[target];

                    /* Include the current element 
                    if it doesn't exceed the target*/
                    bool taken = false;
                    if (arr[ind] <= target)
                        taken = prev[target - arr[ind]];

                    // Update the current row of the DP table
                    cur[target] = notTaken || taken;
                }

                /* Set the current row as the 
                previous row for the next iteration*/
                prev = cur;
            }
            /* The final result is in the last cell
            of the previous row of the DP table*/
            return prev[k];
        }
    }
public:
    /* Function to check if the array can
    be partitioned into two equal subsets*/
    bool equalPartition(int n, vector<int>& arr) {
            
        // Return the result
        return func(n, arr);
    }
};
int main() {
    vector<int> arr = {2, 3, 3, 3, 4, 5};
    int n = arr.size();
    
    //Create an instance of Solution class
    Solution sol;

    if (sol.equalPartition(n, arr))
        cout << "The Array can be partitioned into two equal subsets";
    else
        cout << "The Array cannot be partitioned into two equal subsets";

    return 0;
}
import java.util.*;

class Solution {
    /* Function to check if it's possible to partition
    the array into two subsets with equal sum*/
    private boolean func(int n, int[] arr) {
        int totSum = 0;

        // Calculate the total sum of the array
        for (int i = 0; i < n; i++) {
            totSum += arr[i];
        }

        /* If the total sum is odd, it cannot 
        be partitioned into two equal subsets*/
        if (totSum % 2 == 1)
            return false;
        else {
            int k = totSum / 2;

            /* Initialize a vector to represent
            the previous row of the DP table*/
            boolean[] prev = new boolean[k + 1];
            prev[0] = true;

            /* Initialize the first row based 
            on the first element of the array*/
            if (arr[0] <= k)
                prev[arr[0]] = true;

            // Fill in the DP table using a bottom-up approach
            for (int ind = 1; ind < n; ind++) {
                
                /* Initialize a vector to represent
                the current row of the DP table*/
                boolean[] cur = new boolean[k + 1];
                cur[0] = true;

                for (int target = 1; target <= k; target++) {
                    // Exclude the current element
                    boolean notTaken = prev[target];

                    /* Include the current element 
                    if it doesn't exceed the target*/
                    boolean taken = false;
                    if (arr[ind] <= target)
                        taken = prev[target - arr[ind]];

                    // Update the current row of the DP table
                    cur[target] = notTaken || taken;
                }

                /* Set the current row as the 
                previous row for the next iteration*/
                prev = cur;
            }

            /* The final result is in the last cell 
            of the previous row of the DP table*/
            return prev[k];
        }
    }

    /* Function to check if the array can 
    be partitioned into two equal subsets*/
    public boolean equalPartition(int n, int[] arr) {
        // Return the result
        return func(n, arr);
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 3, 3, 4, 5};
        int n = arr.length;

        // Create an instance of Solution class
        Solution sol = new Solution();

        if (sol.equalPartition(n, arr))
            System.out.println("The Array can be partitioned into two equal subsets");
        else
            System.out.println("The Array cannot be partitioned into two equal subsets");
    }
}
class Solution:
    """ Function to check if it's possible to partition
    the array into two subsets with equal sum"""
    def func(self, n, arr):
        tot_sum = 0

        # Calculate the total sum of the array
        for i in range(n):
            tot_sum += arr[i]

        """ If the total sum is odd, it cannot 
        be partitioned into two equal subsets"""
        if tot_sum % 2 == 1:
            return False
        else:
            k = tot_sum // 2

            """ Initialize a vector to represent the
            previous row of the DP table"""
            prev = [False] * (k + 1)
            prev[0] = True

            """ Initialize the first row based 
            on the first element of the array"""
            if arr[0] <= k:
                prev[arr[0]] = True

            # Fill in the DP table using a bottom-up approach
            for ind in range(1, n):
                """ Initialize a vector to represent
                the current row of the DP table"""
                cur = [False] * (k + 1)
                cur[0] = True

                for target in range(1, k + 1):
                    # Exclude the current element
                    not_taken = prev[target]

                    """ Include the current element 
                    if it doesn't exceed the target"""
                    taken = False
                    if arr[ind] <= target:
                        taken = prev[target - arr[ind]]

                    # Update the current row of the DP table
                    cur[target] = not_taken or taken

                """ Set the current row as the 
                previous row for the next iteration"""
                prev = cur

            """ The final result is in the last cell
            of the previous row of the DP table"""
            return prev[k]

    """ Function to check if the array can 
    be partitioned into two equal subsets"""
    def equalPartition(self, n, arr):
        # Return the result
        return self.func(n, arr)

if __name__ == "__main__":
    arr = [2, 3, 3, 3, 4, 5]
    n = len(arr)

    # Create an instance of Solution class
    sol = Solution()

    if sol.equalPartition(n, arr):
        print("The Array can be partitioned into two equal subsets")
    else:
        print("The Array cannot be partitioned into two equal subsets")
class Solution {
    /* Function to check if it's possible to partition
    the array into two subsets with equal sum*/
    func(n, arr) {
        let totSum = 0;

        // Calculate the total sum of the array
        for (let i = 0; i < n; i++) {
            totSum += arr[i];
        }

        /* If the total sum is odd, it cannot
        be partitioned into two equal subsets*/
        if (totSum % 2 === 1)
            return false;
        else {
            const k = Math.floor(totSum / 2);

            /* Initialize a vector to represent 
            the previous row of the DP table*/
            let prev = new Array(k + 1).fill(false);
            prev[0] = true;

            /* Initialize the first row based 
            on the first element of the array*/
            if (arr[0] <= k)
                prev[arr[0]] = true;

            // Fill in the DP table using a bottom-up approach
            for (let ind = 1; ind < n; ind++) {
                
                /* Initialize a vector to represent
                the current row of the DP table*/
                let cur = new Array(k + 1).fill(false);
                cur[0] = true;

                for (let target = 1; target <= k; target++) {
                    // Exclude the current element
                    let notTaken = prev[target];

                    /* Include the current element
                    if it doesn't exceed the target*/
                    let taken = false;
                    if (arr[ind] <= target)
                        taken = prev[target - arr[ind]];

                    // Update the current row of the DP table
                    cur[target] = notTaken || taken;
                }

                /* Set the current row as the 
                previous row for the next iteration*/
                prev = cur;
            }

            /* The final result is in the last cell
            of the previous row of the DP table*/
            return prev[k];
        }
    }

    /* Function to check if the array can 
    be partitioned into two equal subsets*/
    equalPartition(n, arr) {
        // Return the result
        return this.func(n, arr);
    }
}

const arr = [2, 3, 3, 3, 4, 5];
const n = arr.length;

// Create an instance of Solution class
const sol = new Solution();

if (sol.equalPartition(n, arr)) {
    console.log("The Array can be partitioned into two equal subsets");
} else {
    console.log("The Array cannot be partitioned into two equal subsets");
}

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Observation:

Steps to form the recursive solution:

Complexity Analysis:

Complexity Analysis:

Steps to space optimize the tabulation approach:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code

Facts