Given a set of n integers, divide the set in two subsets, S1 and S2, of n/2 sizes each such that the difference of the sum of two subsets is as minimum as possible. The task is to print that two subset S1 and S2. Elements in S1 and S2 should be present in same format as given in input.
Note:
If n is even, then sizes of two subsets must be strictly n/2
if n is odd, then size of one subset must be (n-1)/2 and size of other subset must be (n+1)/2.
n is strictly greater than 1.
Minimum Diff = abs(s1-s2), where s1>s2.
Example 1:
Input:
arr[] = {3, 4, 5, -3, 100,
1, 89, 54, 23, 20}
Output:
148 148
Explanation: Both output subsets
are of size 5 and sum of elements in
both subsets is same (148 and 148).
So the minimum difference will be 0.
Example 2:
Input:
arr[] = {13, -17, 6, 48, -44, -14}
Output:
-10 2
Explanation: The sums of elements in
two subsets are -10 and 2 respectively.
So the minimum difference will be (2-(-10))
=12.
Your Task:
You don't need to read input or print anything. Complete the function minDifference() which takes N and array arr as input parameters and returns the array which incudes sum of each sub-arrays.

Expected Time Complexity: O(2^N)
Expected Space Complexity: O(2*N)

Constraints:
2 <= N <= 20
-10000 <= arr[i] <= 10000

见题面

见题面