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)

c++

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);
    }
};

• if problem do not have duplicate numbers

• Time : O(nlogn)

• Space : O(1)

c++

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);
    }
};