## Introduction

In this blog, we would be going through a frequently asked medium-rated problem in technical interviews. Consider a problem on subsets on an array of integers where on being given â€˜Nâ€™ integers we need to find the difference between the sum of elements in two different subsets such that their difference is maximised.

Challenging enough!?

So here, we would be taking a look at a brief description and explanation of the same problem along with various approaches that one can take towards solving the problem and we would also be covering the algorithm and the algorithmic complexity analysis on the same.

Must Recommended Topic, __Hash Function in Data Structure____.__

## Problem Statement Description and Explanation

Description: So, here, one would be given a problem which is based on subsets of the array. One would be given an array of â€˜nâ€™ integers. Where the array could contain repetitive elements with the highest frequency of any elements not exceeding two. One needs to make two subsets out of the given array in such a way that the difference of the sum of their elements is maximum and both of them jointly contain all elements of the given array with a crucial additional condition that no subset should contain repetitive elements.

The above problem can be better understood using the example below:

```
Input : a[] = {6, 9, -2, 3}
Output : Maximum Difference of sums of subsets 1 and 2 = 16
Explanation :
Let Subset 1 = {6, 9, 3} and Subset 2 = {-2}
Sum of elements of subset 1 = 18, of subset B = -2
Difference of Sum of Both subsets = 18 - (-2) = 16
Input : arr[] = {6, 9, 6, 5}
Output : Maximum Difference of sums of subsets 1 and 2 = 14
Explanation:
Let Subset 1 = {6, 9, 5} and Subset 2 = {6}
Sum of elements of subset 1 = 20, of subset 2 = 6
Difference of Sum of Both subsets = 20 - 6 = 14
```

For also solving this question one should consider the following conditions which are listed as:

- While building up the subsets, take care that no subset should contain repetitive elements. And for this, we can conclude that all such elements whose frequency is are 2, going to be part of both subsets, and hence overall they donâ€™t have any impact on the difference of subset-sum. So, we can easily ignore them.
- For making the difference of the sum of elements of both subset maximum we have to make the subset in such a way that all positive elements belong to one subset and negative ones to other subsets.