Minimum Subset Sum Difference

Introduction

Dynamic Programming is a technique of for solving problems with multiple overlapping subproblems and optimal substructure properties.

In this blog, we will discuss the minimum subset sum difference problem using recursive and dynamic programming approach. So without any further ado, lets get started!

Problem Statement

The goal is to divide an integer set into two sets, Set A and Set B, with the smallest possible absolute difference between their sums. If a set S has n elements, and we assume Subset A has x, Subset B must have n-x elements, and the value of abs(sum(Subset A) – sum(Subset B)) must be the smallest. The array's elements should all belong to only one of the subsets. Subsets need not have to be contiguous.

Sample Input

**=> arr[ ] = **

1, 2, 3, 5

Output: 1

Explanation: Subset A = {2,3}, sum of Subset1 = 5 Subset B = {5,1}, sum of Subset2 = 6

**=> arr[ ] = **

4, 6, 3, 8

Output: 1

Explanation: Subset A = {4, 6}, sum of Subset1 = 10 Subset B = {3, 8}, sum of Subset2 = 11

Brute Force Approach

The recursive approach involves generating all possible sums from all of the array's values and determining which solution is the most optimal. Either we include the i'th item in set A or we don't, i.e. we include it in set B.

// Recursive C++ code to solve the problem of minimum sum partition. #include <bits/stdc++.h> using namespace std;

// Function to find the minimum sum int find_min(int arr[], int i, int sum_cal, int sum) { if (i == 0) return abs((sum - sum_cal) - sum_cal); return min( find_min(arr, i - 1, sum_cal + arr[i - 1], sum), find_min(arr, i - 1, sum_cal, sum)); }

// Returns the smallest possible difference between two subsets' sums.

int min_diff(int arr[], int n) { // total sum of the elements int sum = 0; for (int i = 0; i < n; i++) sum += arr[i];

return find_min(arr, n, 0, sum); }

// Driver program to test above function int main() { int arr[] = { 1, 2, 3, 5 }; int n = sizeof(arr) / sizeof(arr[0]); cout << "The difference between two sets that is minimum is " << min_diff(arr, n); return 0; }

**Output: **

The least difference between two sets is 1 in the above code.

Time Complexity

By including or excluding the element from set A, all the sums can be generated. So the time complexity will be 22..... *2 (for n times), which is O(2n).

Efficient Approach

The problem can be solved using dynamic programming approach when the sum of the elements is not very large. We can make a 2D array called dp[n+1][sum+1], where n is the number of elements in a set and sum is the total sum of all the elements. We can build the solution in bottom up manner.

The goal is to split the set into two sections. We'll divide it based on the following factors.

Let dp[n+1][sum+1] = {If any subset from 1st to ith index has a sum equal to j, then 1; otherwise, 0}

Here, i varies from {1 to n} and j varies from {0 to (Total sum of the elements)}

So,
dp[n+1][sum+1] will be 1 if: => The sum j can be achieved including the i'th item => The sum j can be achieved excluding the i'th item.

To find the minimum sum difference, we must find j such that Min{sum - j*2 : dp[n][j] == 1 }, where j is a number ranging from 0 to sum/2.

The idea is that Subset A sum is j, and it should be the closest to sum/2, that is, 2*j should be the closest to sum.

The above algorithm is implemented as follows: // A recursive C++ programme to solve the problem of minimum sum // partition. #include <bits/stdc++.h> using namespace std;

// Returns the smallest difference between the two sets.

int find_min(int arr[], int n) { // Calculate sum of all elements int sum = 0; for (int i = 0; i < n; i++) sum += arr[i];

// array to store results of subproblems bool dp[n + 1][sum + 1];

for (int i = 0; i <= n; i++) dp[i][0] = true;

for (int i = 1; i <= sum; i++) dp[0][i] = false;

// Fill the partition table in the bottom up. for (int i = 1; i <= n; i++) { for (int j = 1; j <= sum; j++) { dp[i][j] = dp[i - 1][j];

if (arr[i - 1] <= j) dp[i][j] |= dp[i - 1][j - arr[i - 1]]; } }

int diff = INT_MAX;

// Find the largest j for which dp[n][j] is true, where // j loops from sum/2 to 0 to dp[n][j]. for (int j = sum / 2; j >= 0; j--) { if (dp[n][j] == true) { diff = sum - 2 * j; break; } } return diff; }

// Driver program to test above function int main() { int arr[] = { 1, 2, 3, 5 }; int n = sizeof(arr) / sizeof(arr[0]); cout << "The difference between two sets that is minimum is " << find_min(arr, n); return 0; }

**Output: **

The minimum difference between the two sets i.e. Set A and Set B is 1.

Time Complexity

O(n*sum), where n denotes the number of elements and sum denotes the total number of elements

Space Complexity

O(sum), where sum is the total sum of all the elements in the array.