0

# Partition a set into two subsets such that the difference of subset sums is minimum.

Difficulty: EASY
Avg. time to solve
10 min
Success Rate
85%

Problem Statement
Suggest Edit

#### Note:

``````1. Each element of the array should belong to exactly one of the subset.

2. Subsets need not be contiguous always. 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 Format:
``````The first line of input contains the integer T, denoting the number of test cases.

The first line of each test case contains an integer N, denoting the size of the array.

The second and the last line of each test case contains N space-separated integers denoting the array elements.
``````
##### Output Format:
``````For each test case, print the minimum possible absolute difference in a separate line.
``````
##### Note:
``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 10
1 <= N <= 10^3
0 <= arr[i] <= 10^3

NOTE: It is guaranteed that (N*(sum of all the elements of the array)) <= 10^6

Time Limit: 1sec
``````
##### Sample Input 1:
``````1
4
1 2 3 4
``````
##### Sample Output 1:
``````0
``````
##### Explanation for sample input 1:
``````We can partition the given array into {2,3} and {1,4}, as this will give us the minimum possible absolute difference i.e (5-5=0) in this case.
``````
##### Sample Input 2:
``````1
3
8 6 5
``````
##### Sample Output 2:
``````3
``````
##### Explanation for sample input 2:
``````We can partition the given array into {8} and {6,5}, as this will give us the minimum possible absolute difference i.e (11-8=3) in this case
``````