Have you landed a coding internship or a job interview in your dream company?

If yes, you must not leave any chance to grab this opportunity and this is why practising common coding questions is important to clear your interview with ease.

Therefore, we have come up with a very common question that you can be asked in your coding interview, ie, how to find the minimum subset sum difference?

Here, we have explained to you what the problem is along with all methods that you can use to resolve the problem in the most efficient way. 

Problem Statement

You will be provided with a set S consisting of all integer values. You will have to divide the set into two sets Set1 and Set2 in a way that there is a minimum subset sum difference.

It simply means that if you are given a set S and the subset S1 has n elements then there will be (m-n) elements present in subset S2 in such a way that the abs( sum(s1) - sum(s2)) is minimum.

To understand the problem in a better way, let’s consider the following example:

You are given an array Ar= { 1, 6, 5, 11}

The output of the program will be 1.

Explanation:

S1= { 1, 6, 5}

S2= {11}

The difference between the sum of these subsets is 1.

Methods to Find Minimum Subset Sum Difference

To find the minimum subset sum difference, you can use the following three methods:

• Recursive Solution
• Dynamic programming
• Dynamic programming with less space complexity

Here, let’s discuss all these methods in detail below.

Recursive Approach

The recursive approach is one of the common and basic approaches that you can use to find the minimum subset sum difference. In this method, you will have to generate all the possible sums of the given set of integers and check if the current solution is optimal or not.

Complexity Analysis

• Time Complexity: The time complexity of this method is calculated as O(2 ^n).
• Space Complexity: The space complexity of this method is calculated as O(n).

Dynamic Programming

The brute force or recursion process is quite a space and time-consuming. This is why dynamic programming is preferred to find the minimum subset sum difference of the given set of integers. In this method, you will have to divide the sets into two equal parts and then the problem is solved through subproblems. 

To find the minimum subset sum difference through dynamic programming, here are the steps that you need to follow:

• To begin with, you will have to divide the given set into two sets.
• Now, while you are partitioning it, you will have to keep the following factors in your mind:

1. Let dynamic[n+1][sum+1]= {1 in case any subset from 1st to nth term has a sum equal to elements in j, otherwise, return 0}
2. You will now have to run i from 1 to n and j from 1 to the sum of elements
3. Therefore dynamic[n+1][sum+1] will return 1 in case
4. A Sum of j can be achieved including ith item
5. A Sum of j can be achieved excluding the ith item.
6. Consider the sum of the elements as S.
7. Now, in order to find the minimum sum difference, you will have to find the value of j such that min{sum j*2: dynamic[n][j]==1}. Here, the value of j ranges from 0 to sum/2.

Complexity Analysis

• Time Complexity: The time complexity of this algorithm is calculated as O(n*sum). Here, n denotes the number of elements and sum is the total of all the elements.
• Space Complexity: The space complexity of this algorithm is calculated as O(n*sum).

Dynamic Programming With Less Space Complexity

The dynamic programming method to find the minimum subset sum difference is quite efficient but also space-consuming. Therefore, a more optimized version of dynamic programming can be used to find the subset sum difference.

Here, in this method, rather than using a 2D array, we will resolve the problem with the help of a 1D array i.e., dynamic[sum/2+1].

Considering that the sum of all the elements of set 1 is y, the sum of all elements of set 2 is calculated as sm-x. Here, sm represents the sum of all the elements of Ar.

Therefore, we need to find the minimum abs(sm-2*y).

Moreover, to minimize the difference, we have to find the number which is less than sum/2. This number must be generated by adding all the elements of the array.

Complexity Analysis

• Time complexity: The time complexity of this method is calculated as O(n*sum).
• Auxiliary Space Complexity: The space complexity of this method is calculated as O(sum).

This is how you can find the minimum subset sum difference. 

One similar problem that you may face is the partition equal subset sum problem. Let’s take a look at what this problem is.

Partition Equal Subset Sum Problem

In this problem, you will be provided with an array of N numbers of integers. In this array, you will have to find if you can partition the given array into two equal subsets in equal intervals in such a way that the total of the elements of these intervals is equal. 

To understand better, consider the following example:

You are given an array of integers: [3, 3, 3, 2, 5, 4].

Here, we can partition the given array into two equal subsets, S1= {3, 3, 4} and S2= {3, 2, 5}

The sum of both subsets is 10. 

Conclusion

To find the minimum subset sum difference, three methods can be used. Although using a recursive method is easy, it consumes a lot of time and space. However, using dynamic programming can lead to more space complexity.

Therefore, it is always preferred to use the optimal version of dynamic programming for resolving the minimum subset sum difference problem.