Problem Statement

Given an array arr of n integers, partition the array into two subsets such that the absolute difference between their sums is minimized.

Examples

Example 1:

Input: arr = [1, 7, 14, 15]
Output: 1

Explanation: The array can be partitioned as [1, 7, 5] and [14], with an absolute difference of 1.

Example 2:

Input: arr = [3, 1, 6, 2, 2]
Output: 0

Explanation: The array can be partitioned as [3, 2, 2] and [6, 1], with an absolute difference of 0.

Different Approaches

1️⃣ Recursive Approach

This question is a slight modification of the problem discussed in the Subset Sum equal to target. Before discussing the approach for this question, it is important to understand what we did in the previous question of the Subset Sum equal to the target. There we found whether or not a subset exists in an array with a given target sum.

In this question, we need to partition the array into two subsets( say with sum S1 and S2) and we need to return the minimized absolute difference of S1 and S2. But do not need two variables for it. We can use a variable 'totSum', which stores the sum of all elements of the input array, and then we can simply say S2 = totSum - S1. Therefore we only need one variable S1.

From here try to find a subset in the array with a target as discussed in Subset Sum equal to the target.

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.

Intuition:

The goal is to divide the given array into two subsets such that the absolute difference between their sums is minimized. To achieve this, we leverage the concept of the Subset Sum Problem, where we determine if a subset with a particular sum exists.

1. Subset Sum Problem:
   Given an array, check if a subset exists with a specific target sum. Here, we compute all subset sums that can be formed by including or excluding elements.
2. Key Observation:
   If the total sum of the array is totalSum, and one subset has a sum subsetSum, the other subset's sum is totalSum - subsetSum.
   Therefore, the absolute difference between the two subsets is:
3. Minimizing the Difference:
   • Generate all possible subset sums (subsetSum).
   • For each subsetSum, compute the corresponding absolute difference.
   • Track the minimum difference.

Approach:

1. Total Sum Calculation:
   • Compute the total sum of all elements in the array: totalSum.
2. Subset Sum Check:
   • Use a recursive function to determine if a subset with a given targetSum can be formed:
     • Include the current element in the subset (reduce targetSum).
     • Exclude the current element and move to the next.
3. Iterate Over Subset Sums:
   • Iterate over all possible values of subsetSum from 0 to totalSum.
   • For each valid subset sum:

     • Calculate the difference using the formula:

       Difference = |subsetSum - (totalSum - subsetSum)|

     • Update the minimum difference.
4. Return the Result:
   • Return the minimum absolute difference encountered.

Dry Run:

Input:

nums = {1, 2, 3, 4}

Step 1: Total Sum Calculation:

totalSum = 1 + 2 + 3 + 4 = 10

Step 2: Subset Sum Calculation:

• Generate all possible subsets sums using recursion:
  • 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.

Step 3: Minimize the Difference

For each valid subsetSum, calculate the absolute difference:

Step 4: Minimum Difference

The minimum absolute difference is 0 when:

subsetSum = 5
otherSubsetSum = 5

Code:

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

class Solution {
private:
    // Recursive function to determine if a subset with a given target sum exists
    bool isSubsetSumPossible(int index, int targetSum, vector<int>& nums) {
        // Base Case 1: If the target sum is achieved, return true
        if (targetSum == 0)
            return true;

        // Base Case 2: If we have reached the first element
        if (index == 0)
            return (nums[0] == targetSum);

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

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

        // Return true if either including or excluding the current element works
        return excludeCurrent || includeCurrent;
    }

public:
    // Function to find the minimum absolute difference between two subset sums
    int minSubsetSumDifference(vector<int>& nums, int n) {
        int totalSum = 0;

        // Step 1: Calculate the total sum of the array
        for (int i = 0; i < n; i++) {
            totalSum += nums[i];
        }

        /* Step 2: Check all possible subset sums from 0 to totalSum.
           Use a recursive function to determine if a subset with a given sum exists. */
        int minimumDifference = INT_MAX;

        for (int subsetSum = 0; subsetSum <= totalSum; subsetSum++) {
            if (isSubsetSumPossible(n - 1, subsetSum, nums)) {
                // Calculate the sum of the other subset
                int otherSubsetSum = totalSum - subsetSum;

                // Update the minimum difference
                int currentDifference = abs(subsetSum - otherSubsetSum);
                minimumDifference = min(minimumDifference, currentDifference);
            }
        }

        return minimumDifference;
    }
};

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

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

    // Call the function and print the result
    cout << "The minimum absolute difference is: " << solution.minSubsetSumDifference(nums, n) << endl;

    return 0;
}

Explanation:

• Recursive Function (isSubsetSumPossible):
  • Determines whether a subset with a given targetSum can be formed using elements up to the given index.
  • Uses two choices at each step:
    • Exclude the current element.
    • Include the current element if it does not exceed the targetSum.
• minSubsetSumDifference Function:
  • Iterates over all possible subset sums (0 to totalSum).
  • For each valid subset sum (where isSubsetSumPossible returns true), calculates the absolute difference between two subsets.
  • Keeps track of the minimum absolute difference.

Complexity Analysis:

• Time Complexity:
  • The recursive function isSubsetSumPossible explores O(2^n) possibilities.
  • Checking all subset sums from 0 to totalSum takes O(totalSum) iterations.
  • Overall time complexity: O(2^n * totalSum).
• Space Complexity:
  • The recursion stack consumes O(n) space for depth of recursion.

2️⃣ Memoization:

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

Code:

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

class Solution {
private:
    // Recursive function to determine if a subset with a given target sum exists
    bool isSubsetSumPossible(int index, int targetSum, vector<int>& nums, vector<vector<int>>& dp) {
        // Base Case 1: If the target sum is achieved, return true
        if (targetSum == 0) return true;

        // Base Case 2: If we have reached the first element
        if (index == 0) return (nums[0] == targetSum);

        // If the result has already been computed, return it from dp
        if (dp[index][targetSum] != -1) return dp[index][targetSum];

        // Option 1: Exclude the current element
        bool excludeCurrent = isSubsetSumPossible(index - 1, targetSum, nums, dp);

        // Option 2: Include the current element if it does not exceed targetSum
        bool includeCurrent = false;
        if (nums[index] <= targetSum)
            includeCurrent = isSubsetSumPossible(index - 1, targetSum - nums[index], nums, dp);

        // Store the result in dp
        dp[index][targetSum] = (excludeCurrent || includeCurrent);

        return dp[index][targetSum];
    }

public:
    // Function to find the minimum absolute difference between two subset sums
    int minSubsetSumDifference(vector<int>& nums, int n) {
        int totalSum = 0;

        // Step 1: Calculate the total sum of the array
        for (int i = 0; i < n; i++) {
            totalSum += nums[i];
        }

        // Step 2: Create a memoization table initialized to -1
        vector<vector<int>> dp(n, vector<int>(totalSum + 1, -1));

        // Step 3: Check all possible subset sums from 0 to totalSum.
        int minimumDifference = INT_MAX;

        for (int subsetSum = 0; subsetSum <= totalSum; subsetSum++) {
            if (isSubsetSumPossible(n - 1, subsetSum, nums, dp)) {
                // Calculate the sum of the other subset
                int otherSubsetSum = totalSum - subsetSum;

                // Update the minimum difference
                int currentDifference = abs(subsetSum - otherSubsetSum);
                minimumDifference = min(minimumDifference, currentDifference);
            }
        }

        return minimumDifference;
    }
};

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

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

    // Call the function and print the result
    cout << "The minimum absolute difference is: " << solution.minSubsetSumDifference(nums, n) << endl;

    return 0;
}

Complexity Analysis:

• Time Complexity:
  • The recursion tree has O(n * totalSum) nodes (where n is the number of elements and totalSum is the sum of all elements). Each node is visited once and the result is stored, so the time complexity becomes O(n * totalSum).
• Space Complexity:
  • The space complexity is dominated by the memoization table (dp), which has a size of O(n * totalSum). Additionally, the recursion stack has a depth of O(n). Thus, the overall space complexity is O(n * totalSum).