1
\$\begingroup\$

Given an array and a value x, I need an algorithm to find the minimum number of items to pick from the array so that the difference between the sum of those items and x is minimal.

public class Demo {

    static int[] solve(int arr[], int i, int esum, int csum, int size) {

        if (i == 0) {
            return new int[]{Math.abs(esum - csum), size};
        }

        int a1[] = solve(arr, i - 1, esum, csum + arr[i - 1], size + 1);
        int a2[] = solve(arr, i - 1, esum, csum, size);

        if (a1[0] < a2[0]) {
            return a1;
        } else if (a1[0] > a2[0]) {
            return a2;
        } else {
            if (a1[1] < a2[1]) {

                return a1;
            } else {
                return a2;
            }
        }
    }

    public static void main(String[] args) {
        //x = 108
        int arr[] = new int[]{70, 30, 33, 23, 4, 4, 34, 95, -50, -10, -10, -7};
        int a[] = solve(arr, arr.length, 108, 0, 0);
        System.out.println(a[0] + " " + a[1]);

    }
}

The output should be 0,3 (absolute difference), (number of items)

The first preference is the minimum absolute difference, only if there's multiple subsets with the same absolute difference we pick the one with the least number of items.

\$\endgroup\$
0

1 Answer 1

0
\$\begingroup\$

Scope

    static int[] solve(int arr[], int i, int esum, int csum, int size) {

You leave this as the default scope. For Java, this is package private.

In this case, I would go with

    private static int[] solve(int arr[], int i, int esum, int csum, int size) {

The reason being that three of these parameters (i, csum, size) reflect internal knowledge of how the method works. So I would make this private to make it clear that only people editing this class should use this method. I would then add an additional method:

    public static int[] solve(int targetSum, int... numbers) {
        return solve(numbers, numbers.length, targetSum, 0, 0);
    }

This offers a public face to the private implementation.

I find names like numbers and targetSum easier to read than arr and esum. In fact, I still don't know what esum is except by inspecting what it does. Ideally, names should make it easier for me to understand the code.

This also allows solve to be called in more ways. You can still call it

    solve(108, arr);

But you can also say

    solve(108, 70, 30, 33, 23, 4, 4, 34, 95, -50, -10, -10, -7);

If that happens to be easier.

This may not matter in real usage, but often it's easier to test in the latter form.

Object oriented

I would also consider making a class to hold the solution. As is, the solution is held in a magic version of an int array. What's in the array? Which element is which? Again, we have to go read the code to know. I'd rather just be able to read an interface. E.g.

public class PartialSum {

     private int distance;
     private int count;

     public PartialSumDistance(int distance, int count) {
         this.distance = distance;
         this.count = count;
     }

     public getDistance() {
         return distance;
     }

     public getSize() {
         return count;
     }

}

Now, instead of saying a1[0], I can say a1.getDistance(), which is much clearer about what is being discussed.

Optimizing the end condition

        if (i == 0) {

Consider

        if (i == 0 || esum == csum) {

If we have found a matching partial sum, we can never get closer to a solution. We can only add additional items. But smaller solutions are better. So once we've found a matching sum, we can return. This branch has nothing more to show us. We've already found the best solution that it could find.

Sorting

If the input array were sorted (ascending), we could say

        if (csum < esum && arr[i - 1] < 0) {

And return the current solution. We are currently as close to a solution as we could be.

Overall, there are \$2^n\$ sums to check where \$n\$ is the number of items in the array. This is because each item can either be in or not in the sum. So enumerating all the sums is \$\mathcal{O}(2^n)\$. Sorting is only \$\mathcal{O}(n \log n)\$. So we can sort for a trivial cost compared to the overall time to process the problem. Meanwhile, we can potentially prune \$2^i\$ checks, where i is the number of elements remaining in the array as we process it. Since i is potentially equal to \$n\$, this seems worthwhile.

Further optimization

To optimize further, we'd need to know more about how the data was meant to be used. For example, if the number of targets to search is larger relative to \$2^n\$, it might make sense to pregenerate all the partial sums and put them in a NavigableMap or NavigableSet. Then we could just fetch the appropriate value. But that would be a lousy solution if we're only going to look up one target per array.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.