Minimum Subset Sum Difference
Application of Concept of 0/1 Knapsack

Algorithms and Data Structures: TheAlgorist.com

System Design: www.System.Design

Low Level Design: LowLevelDesign.io

Frontend Engineering: FrontendEngineering.io
জয় শ্রী রাম
🕉
Problem Statement:
Given an integer array A containing N integers.
You need to divide the array A into two subsets S1 and S2 such that the absolute difference between their sums is minimum.
Find and return this minimum possible absolute difference.
NOTE:
Subsets can contain elements from A in any order (not necessary to be contiguous).
Each element of A should belong to any one subset S1 or S2, not both.
It may be possible that one subset remains empty.
Example:
Input 1:
A = [1, 6, 11, 5]
Output: 1
Explanation:
Subset1 = {1, 5, 6}, sum of Subset1 = 12
Subset2 = {11}, sum of Subset2 = 11
Input 2:
A = [6]
Output: 6
Explanation:
Subset1 = {6}, sum of Subset1 = 6
Subset2 = {}, sum of Subset2 = 0
Solution:
Please go through Subset Sum Problem before solving this problem.
We would be able to solve this problem by extending Subset Sum Problem. Notice that the maximum sum of a subset can be the sum of all the elements. Example: {6}
So we compute subset sum for target sum = sum of all elements.
Next thing to notice is it is impossible that we have two subsets and both of them has subset sum > (total sum of all elements) / 2. We would need this observation while writing our code. The algorithm for this problem is simple. Please take a look at the code below:
Java Code:
Login to Access Content
Python Code:
Login to Access Content