Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Problem of the day

You are given an array **'arr'****'n'**

Your task is to partition this array into two subsets such that the absolute difference between subset sums is minimum.

You just need to find the minimum absolute difference considering any valid division of the array elements.

Note:

```
1. Each array element should belong to exactly one of the subsets.
2. Subsets need not always be contiguous.
For example, for the array : [1, 2, 3], some of the possible divisions are
a) {1,2} and {3}
b) {1,3} and {2}.
3. Subset-sum is the sum of all the elements in that subset.
```

```
Input: 'n' = 5, 'arr' = [3, 1, 5, 2, 8].
Ouput: 1
Explanation: We can partition the given array into {3, 1, 5} and {2, 8}.
This will give us the minimum possible absolute difference i.e. (10 - 9 = 1).
```

Detailed explanation

```
4
1 2 3 4
```

```
0
```

```
We can partition the given array into {2,3} and {1,4}.
This will give us the minimum possible absolute difference i.e. (5 - 5 = 0) in this case.
```

```
3
8 6 5
```

```
3
```

```
We can partition the given array into {8} and {6,5}.
This will give us the minimum possible absolute difference i.e. (11 - 8 = 3).
```

```
The expected time complexity is O(n * 𝚺 'arr'[i]), where 𝚺 'arr'[i] denotes the sum of all elements in 'arr'.
```

```
1 <= 'n' <= 10^3
0 <= 'arr'[i] <= 10^3
0 <= 𝚺 'arr'[i] <= 10^4,
where 𝚺 'arr'[i] denotes the sum of all elements in 'arr'.
Time Limit: 1sec
```