Minimum sum partition
Given an integer array arr of size N, 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
Time : O(n * sum)
Space : O(sum)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution {public : int minDifference (int arr[], int n) { int sum = 0 , ma = 0 ; for (int i = 0 ; i < n; i++) sum += arr[i]; vector<int > dp (sum / 2 + 1 , 0 ) ; dp[0 ] = 1 ; for (int i = 0 ; i < n; i++) { for (int j = sum / 2 ; j >= arr[i]; j--) { if (dp[j - arr[i]]) { dp[j] = 1 ; ma = max (ma, j); } } } return abs (sum - 2 * ma); } };
1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution {public : int minDifference (int arr[], int n) { sort (arr, arr + n); int diff = 0 ; for (int i = n - 1 ; i >= 0 ; i--) { if (diff >= 0 ) diff -= arr[i]; else diff += arr[i]; } return abs (diff); } };