• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.
  • If you are a student, email to admin@thealgorists.com to get special student discount.



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:



This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.




The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave