Problem Statement

Given an array arr of n integers, return true if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal else return false.

Examples

Example 1:

Input: arr = [1, 10, 21, 10]
Output: True

Explanation: The array can be partitioned as [1, 10, 10] and [21]

Example 2:

Input: arr = [1, 2, 3, 5]
Output: False

Explanation: The array cannot be partitioned into equal sum subsets.

Different Approaches

1️⃣ Recursive Approach

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 two 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.

Code:

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

class Solution {
private:
    /* Function to determine if it's possible to form a subset
    with the given target sum using elements up to the current index */
    bool canFormSubset(int currentIndex, int targetSum, vector<int>& nums) {
        // Base case: If the target sum is 0, a valid subset is found
        if (targetSum == 0)
            return true;

        // Base case: If we are at the first element, check if it equals the target sum
        if (currentIndex == 0)
            return nums[0] == targetSum;

        // Option 1: Exclude the current element
        bool excludeCurrent = canFormSubset(currentIndex - 1, targetSum, nums);

        // Option 2: Include the current element (only if it does not exceed the target sum)
        bool includeCurrent = false;
        if (nums[currentIndex] <= targetSum)
            includeCurrent = canFormSubset(currentIndex - 1, targetSum - nums[currentIndex], nums);

        // Return true if either option is successful
        return excludeCurrent || includeCurrent;
    }

public:
    /* Function to check if the array can be partitioned into
    two subsets with equal sum */
    bool canPartition(vector<int>& nums) {
        int totalSum = 0;

        // Calculate the total sum of the array
        for (int num : nums) {
            totalSum += num;
        }

        // If the total sum is odd, it cannot be partitioned into two equal subsets
        if (totalSum % 2 != 0)
            return false;

        // Target sum for each subset (half of the total sum)
        int targetSum = totalSum / 2;

        // Call the helper function to check if a subset with the target sum exists
        return canFormSubset(nums.size() - 1, targetSum, nums);
    }
};

int main() {
    vector<int> nums = {2, 3, 3, 3, 4, 5};
    int n = nums.size();

    // Create an instance of the Solution class
    Solution sol;

    // Check if the array can be partitioned into two equal subsets
    if (sol.canPartition(nums))
        cout << "The array can be partitioned into two equal subsets" << endl;
    else
        cout << "The array cannot be partitioned into two equal subsets" << endl;

    return 0;
}

Complexity Analysis:

• Time Complexity: O(2^(N)), where N is the length of the array. As, for each index, there are two possible options.
• Space Complexity: O(N), at maximum the depth of the recursive stack can go upto N.