PROBLEM DESCRIPTION
Given an array arr of size n containing non-negative integers, the task is to divide it into two sets S1 and S2 such that the absolute difference between their sums is minimum and find the minimum difference
SOLUTION
BRUTE FORCE (TLE)
We can form all subsets using the array elements and track its sum using recursion and backtracking. The sum of second subset will be totalSum - sumOfSubset1. Keep updating the minimum possible value.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution
{
public int minDifference(int arr[], int n)
{
// total sum of the array elements
int sum = 0;
for(int i = 0; i < n; i++)
sum += arr[i];
minDifferenceHelper(arr, n, sum, new ArrayList<>(), 0, 0);
return minDiff;
}
int minDiff = Integer.MAX_VALUE;
public void minDifferenceHelper(int[] arr, int n, int totalSum, List<Integer> list, int currentSum, int idx)
{
// Base case: If we've processed all elements
if(idx == n)
{
// Calculate the sum of one subset (currentSum) and the other subset (totalSum - currentSum)
int x = currentSum;
int y = totalSum - currentSum;
// Update the minimum difference between the two subset sums
minDiff = Math.min(minDiff, Math.abs(x - y));
return;
}
// Decision 1: Include the current element in the subset
list.add(arr[idx]); // Add the element to the subset
minDifferenceHelper(arr, n, totalSum, list, currentSum + arr[idx], idx + 1); // Recur for the next element
list.remove(list.size() - 1); // Backtrack to explore other possibilities
// Decision 2: Exclude the current element from the subset
minDifferenceHelper(arr, n, totalSum, list, currentSum, idx + 1); // Recur for the next element without adding the current element
}
}
SMALL OPTIMIZATION (TLE)
We don’t really need to maintain the subset1 elements. We can just keep a track of the current sum, if we include the current element at index idx or not.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution
{
public int minDifference(int arr[], int n)
{
int sum = 0;
for(int i=0; i<n; i++)
sum += arr[i];
minDifferenceHelper(arr, n, sum, 0, 0);
return minDiff;
}
int minDiff = Integer.MAX_VALUE;
public void minDifferenceHelper(int[] arr, int n, int totalSum, int currentSum, int idx){
if(idx == n){
int x = currentSum;
int y = totalSum - currentSum;
minDiff = Math.min(minDiff, Math.abs(x-y));
return;
}
// take
minDifferenceHelper(arr, n, totalSum, currentSum + arr[idx], idx + 1);
// don't take
minDifferenceHelper(arr, n, totalSum, currentSum, idx+1);
}
}