🙏

জয়  শ্রী  রাম

🕉

---

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

Instructor: