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 as the result.

Calculate the total sum of all elements and define the target as any sum between 0 and total sum.
Use a recursive function with parameters: index, current sum, and a DP table for memoization.
At each step, choose to include or exclude the current element and explore both possibilities.
Store results in the DP table to avoid recomputation for the same index and sum.
After filling the table, iterate over possible sums to find the minimal absolute difference between two subsets.

Code

1234567<