Dynamic programming partition array to find minimum difference fails for negative numbers

Question

I am trying to solve the problem it works for positive integer arrays but fails for negative test cases. How to handle the below test case?

You are given an integer array nums of 2 * n integers. You need to partition nums into two arrays of length n to minimize the absolute difference of the sums of the arrays. To partition nums, put each element of nums into one of the two arrays. Return the minimum possible absolute difference.

I am able to get the possible sum for these negative numbers and store in the list of the map but, when I iterate through the map values to find the absolute difference I cannot get the correct value as 0 instead I am getting the value as 6 because in the memorization map possible sum as -3 added it to the target we get 3. so the absolute difference becomes 6

How to handle this scenario? Refer to the below comment in the code.

Code that needs to re-visited for negative integers scenario

Test case: Input: nums = [2,-1,0,4,-2,-9] Output: 0 Explanation: One optimal partition is: [2,4,-9] and [-1,0,-2]. The absolute difference between the sums of the arrays is abs((2 + 4 + -9) - (-1 + 0 + -2)) = 0.

package com.dynamicProgramming;

import java.util.*;

public class PartitionSum {

    List<HashMap<Integer,Boolean>> ll = new ArrayList<>();

    public int minimumDifference(int[] nums) {
        int n = nums.length;
        int range = 0;
        for(int i =0;i<nums.length;i++){
            ll.add(new HashMap<>());
            range+=nums[i];
        }
       // System.out.println(range/2);
        findSub(nums ,n-1,range);
       int min=Integer.MAX_VALUE;
//Code that needs to re-vistied for negative integers scenario
       for(HashMap<Integer,Boolean> h:ll){

           for(Map.Entry<Integer,Boolean> map:h.entrySet()){

               if(map.getValue()){

                   int s2= (range<0)?range+map.getKey():range-map.getKey();

                   System.out.println(map.getKey()+ " "+s2);
                   int diff=Math.abs(s2-map.getKey());
                   min=Math.min(min,diff);
               }
           }
       }
        return min;
    }

    private boolean findSub(int[] nums, int i, int sum) {

        if(sum==0)
            return true;
        if(i==0){
            return nums[i]==sum;
        }

        if(ll.get(i).containsKey(sum)) {
            return ll.get(i).get(sum);

        }
        boolean p=false;
        if(sum>=nums[i])
            p=findSub(nums,i-1,sum-nums[i]);
        boolean np=findSub(nums,i-1,sum);
        ll.get(i).put(sum,p||np);
        return p||np;


    }


    public static void main(String[] args) {
        PartitionSum partitionSum= new PartitionSum();
        int[] nums={2,-1,0,4,-2,-9};

        System.out.println(partitionSum.minimumDifference(nums));
        System.out.println(partitionSum.ll);
    }

}

Answer 1

Since n is quite small, you can split the array into two halves, then brute force over all possible subsets. Then, combine the results to attempt to get as close as possible to half the sum of the original array. This would be one of the arrays of size n in the partition.

public int minimumDifference(int[] nums) {
    int n = nums.length / 2, overallSum = Arrays.stream(nums).sum();
    TreeSet<Integer>[] leftSums = new TreeSet[n + 1];
    Arrays.setAll(leftSums, i -> new TreeSet<>());
    for (int i = 0; i < 1 << n; i++) {
        int size = 0, sum = 0;
        for (int j = 0; j < n; j++)
            if ((i >> j & 1) != 0) {
                sum += nums[j];
                ++size;
            }
        leftSums[size].add(sum);
    }
    int ans = Integer.MAX_VALUE;
    for (int i = 0; i < 1 << n; i++) {
        int size = 0, sum = 0;
        for (int j = 0; j < n; j++)
            if ((i >> j & 1) != 0) {
                sum += nums[n + j];
                ++size;
            }
        Integer floor = leftSums[n - size].floor(overallSum / 2 - sum),
                ceiling = leftSums[n - size].ceiling(overallSum / 2 - sum);
        if (floor != null) ans = Math.min(ans, Math.abs(overallSum - 2 * (sum + floor)));
        if (ceiling != null) ans = Math.min(ans, Math.abs(overallSum - 2 * (sum + ceiling)));
    }
    return ans;
}

Answer 2

Here is a recursive approach that's more or less brute force with memoisation, tracking the state as the differences between the two bags' sums and size.

private static int f(int[] A) {
    return f(A, 1, A[0], 1, new HashMap<>());
}

private static int f(int[] A, int i, int diff, int sizeDiff, Map<List<Integer>, Integer> memo) {
    if (i == A.length) {
        return Math.abs(diff);
    }

    List<Integer> key = List.of(i, diff, sizeDiff);
    if (memo.containsKey(key)) {
        return(memo.get(key));
    }

    int best = Integer.MAX_VALUE;

    if (sizeDiff < 0 || A.length - i > sizeDiff) {
        best = Math.min(best,
            f(A, i + 1, diff + A[i], sizeDiff + 1, memo));
    }

    if (sizeDiff >= 0 || A.length - i > -sizeDiff) {
        best = Math.min(best,
            f(A, i + 1, diff - A[i], sizeDiff - 1, memo));
    }

    memo.put(key, best);

    return best;
}