The Maximum possible difference of the sum of two subsets of an array

Bruteforce Approach

The brute-force approach here focuses on checking whether the elements present in the array appear once or twice in it. If the element is present in the array twice then we don’t include the sum of the element in either of the subsets as it would end up cancelling out. 

If the element appears just once then we keep adding it to the first subset-sum if the element is positive and to the other subset-sum in case the element is negative. 

for i=0 to n-1
    appearsOnce = true;
    for  j= i+1 to n-1
        // if frequency of any element is two
        // make both equal to zero
        if arr[i] equals arr[j]
            arr[i] = arr[j] = 0
            appearsOnce = false;
            break;
    if appearsOnce == true
        if (arr[i] > 0)
            firstSubsetSum += arr[i];
        else 
            secondSubsetSum += arr[i];
return abs(firstSubsetSum - secondSubsetSum)

Algorithm Complexity

Time Complexity: O(N^2)

Here we are traversing two nested loops that will be O(N^2).

Space Complexity: O(1)

Since we are using no extra space for the intermediate steps it makes the space complexity a constant.

Sorting First

This approach is an optimised brute-force approach where one sorts the array first and then checks whether the elements present in the array appear once or twice in it and then checks and follows the same set of steps as the brute force approach.

-> first sort the array
-> for i =0 to n-2
      // if subsequent two elements are not equal
      // then add the absolute value of arr[i] to the result
      if arr[i] != arr[i+1]
          result += abs(arr[i])
      // else skip the next element as well
      else
          i++;
          
// specific check for the last two elements
-> if (arr[n-2] != arr[n-1])
    result += arr[n-1]

-> return result;

Algorithm Complexity

Time Complexity: O(N*log(N))

Here we are traversing only once in a loop that will be O(N), and for sorting the vector, it will be (N*log(N)).

Space Complexity: O(1)

Since we are using no extra space for the intermediate steps it makes the space complexity a constant.

Hashtable-Based Approach

This is an optimised approach to the problem where one builds the hashmap/hashtable of the frequency values of the elements in the array after which one can follow the same set of steps as the other approaches to find the maximum difference between the subset sums.

make hash table for positive elements:
    for all positive elements(arr[i])
        if frequency == 1
            firstSubsetSum += arr[i];
make hash table for negative elements:
    for all negative elements
        if frequency == 1
            secondSubsetSum += arr[i];
return abs(firstSubsetSum - secondSubsetSum)

Algorithm Complexity

Time Complexity: O(N)

Here we are traversing only once in a loop that will be O(N) after we created a hashtable of the counts of the frequencies for the elements present in the array.

Space Complexity: O(N)

Here, we are using an additional space to create a hashtable (unordered_map in C++) that will take O(N) space in the worst case.

Frequently Asked Questions

How do we store values in a hash table?

In the hash table, we store values in the form of key-value pairs.

How many total subsets can be formed from an array of size N?

From an array of size N, you can form 2^N subsets.

What is the time complexity of hashing?

The overall time complexity of the hash function is O(1).

Which Among the two - map or an unordered_map, uses hashing to store elements?

unordered_map uses hashing to store the elements.

Why is hashmap preferred over hashtable in some scenarios?

Usually, they both are preferred equally, but in the case of NULL keys, hashmap can store them, whereas hashtable cannot store NULL keys.

Conclusion

In this blog, We have extensively discussed various approaches to solve the problem of finding the maximum difference from a given array between two different subsets sums. This problem is often rated and categorised as a Medium to a Hard Level problem.

Recommended problems -

• Max circular subarray sum
• Shortest subarray with sum at least k
• Maximum sum subarray of size k
• Subarray sums divisible by k
• Sum of two arrays

To practice more problems similar to this one, you can refer here Minimize Partitioned Subset Sum in an array. Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enrol in our courses, refer to the mock test and problems; look at the interview experiences and interview bundle for placement preparations.

Do upvote our blog to help other ninjas grow.

Happy Learning!