Input: nums = [1, 2, 3, 4]
Output: 0
Explanation: Two subsets can be [1,4] and [2,3].


Input: nums = [8, 6, 5]
Output: 3 
Explanation: Two subsets can be [8] and [6, 5].

Disclaimer: Here is the practice link to help you assess your knowledge better. It's highly recommend trying to solve it before looking at the solution.

Memoization

Algorithm

This question is a slight modification of the problem discussed in Subset-sum equal to target. There we found whether or not a subset exists in an array with a given target sum. We used a dp array to get to our answer. We used to return dp[n-1][k] as our answer. One interesting thing that is happening is that for calculating our answer for dp[n-1][k], we are also solving multiple sub-problems and at the same time storing them as well. We will use this property to solve the question of this article.

In this problem, we want to divide the array into two subsets and return the smallest possible absolute difference between their sums. But instead of tracking both sums separately, we can simplify the process. If we know the total sum of the array and the sum of any one subset, then sum of other subset can be calculated by taking difference of total sum and subset sum. This means we only need to keep track of sum of one subset.

The first subset’s sum can range from 0 to the total sum of the array. The last row of the DP table shows which sums are possible. For each possible sum, we find the other subset’s sum, compute their absolute difference, and take the minimum among them a