0
\$\begingroup\$

Given a set of \$n\$ integers, divide the set in two subsets of \$\frac{n}{2}\$ sizes each such that the difference of the sum of two subsets is as minimum as possible. If \$n\$ is even, then sizes of two subsets must be strictly \$\frac{n}{2}\$ and if \$n\$ is odd, then size of one subset must be \$\frac{n-1}{2}\$ and size of other subset must be \$\frac{n+1}{2}\$.

For example, let a given set be {3, 4, 5, -3, 100, 1, 89, 54, 23, 20}, the size of set is 10. Output for this set should be {4, 100, 1, 23, 20} and {3, 5, -3, 89, 54}. Both output subsets are of size 5 and sum of elements in both subsets is same (148 and 148). Let us consider another example where n is odd. Let given set be {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}. The output subsets should be {45, -34, 12, 98, -1} and {23, 0, -99, 4, 189, 4}. The sums of elements in two subsets are 120 and 121 respectively.

Also verifying complexity:

  • Time - \$O(2^n)\$
  • Space - \$O(n)\$

where \$n\$ is the array size.

Looking for code review, optimizations and best practices.

final class DataSet {
    private final List<Integer> firstHalf;
    private final List<Integer> secondHalf;

    public DataSet(List<Integer> firstHalf, List<Integer> secondHalf) {
        this.firstHalf = firstHalf;
        this.secondHalf = secondHalf;
    }

    public List<Integer> getFirstHalf() {
        return this.firstHalf;
    }

    public List<Integer> getSecondHalf() {
        return this.secondHalf;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((firstHalf == null) ? 0 : firstHalf.hashCode());
        result = prime * result + ((secondHalf == null) ? 0 : secondHalf.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        DataSet other = (DataSet) obj;
        if (firstHalf == null) {
            if (other.firstHalf != null)
                return false;
        } else if (!firstHalf.equals(other.firstHalf))
            return false;
        if (secondHalf == null) {
            if (other.secondHalf != null)
                return false;
        } else if (!secondHalf.equals(other.secondHalf))
            return false;
        return true;
    }
}


public final class TugOfWar {

    private TugOfWar() { }

   /**
    * Returns dataset of 2 lists, such that each list contains 
    * subsets of original array, such that different of the sum of individual list is minimal.
    * 
    * @param a the input array
    * @return  the dataset
    */
    public static DataSet doTug (int[] a) {

        final Set<Integer> secondHalf = new HashSet<Integer>();
        for (int i : a) {
            secondHalf.add(i);
        }

        final Set<Integer> resultFirstHalf = new HashSet<Integer>();
        final Set<Integer> resultSecondHalf = new HashSet<Integer>();

        compute(a,  new HashSet<Integer>(), secondHalf, resultFirstHalf, resultSecondHalf);

        return new DataSet(new ArrayList<Integer>(resultFirstHalf), new ArrayList<Integer>(resultSecondHalf));
    }

    private static void compute (int[] a, Set<Integer> firstHalf, Set<Integer> secondHalf, Set<Integer> prevFirstHalf,  Set<Integer> prevSecondHalf) {

        if (firstHalf.size() == secondHalf.size() || firstHalf.size() == secondHalf.size() - 1) {
            int diff = setSumDiff(firstHalf, secondHalf);
            int prevDiff = setSumDiff(prevFirstHalf, prevSecondHalf);

            // prevFirstHalf.size() == 0, by that we mean the very first time we hit this condition.
            if (diff <= prevDiff || prevFirstHalf.size() == 0) {
                prevFirstHalf.clear();
                prevSecondHalf.clear();

                prevFirstHalf.addAll(firstHalf);
                prevSecondHalf.addAll(secondHalf);
            }
        }

        for (int i : a) {
            if (secondHalf.contains(i)) {
                firstHalf.add(i);
                secondHalf.remove(i);

                compute(a, firstHalf, secondHalf, prevFirstHalf, prevSecondHalf);

                firstHalf.remove(i);
                secondHalf.add(i);
            }
        }
    }

    private static int setSumDiff(Set<Integer> firstHalf, Set<Integer> secondHalf) { 
        int diff = 0;
        for (int i  : firstHalf) {
            diff = diff + i;
        }
        for (int i : secondHalf) {
            diff = diff - i;
        }
        return Math.abs(diff);
    }

}


public class TugOfWarTest {

    @Test
    public void test1 ( ) {
        int[] a1 = { 3, 4, 5, -3, 100, 1, 89, 54, 23, 20 };

        List<Integer> list1 = new ArrayList<Integer>();
        list1.add(1);
        list1.add(100);
        list1.add(4);
        list1.add(20);
        list1.add(23);
        List<Integer> list2 = new ArrayList<Integer>();
        list2.add(3);
        list2.add(5);
        list2.add(54);
        list2.add(89);
        list2.add(-3);

        assertEquals(new DataSet(list1, list2), TugOfWar.doTug(a1));
    }

    @Test
    public void test2 () {
        int[] a2 = { 1, 2, 3, 4 };

        List<Integer> list3 = new ArrayList<Integer>();
        list3.add(1);
        list3.add(4);
        List<Integer> list4 = new ArrayList<Integer>();
        list4.add(2);
        list4.add(3);

        assertEquals(new DataSet(list3, list4), TugOfWar.doTug(a2));
    }
}
\$\endgroup\$
2
\$\begingroup\$

Regarding the "set" it is debatable. If it is a set in mathematical terms then it means that no two elements can be there twice so using Java Set would not be a problem.

However, if you are solving this problem in an environment where you are absolutely sure that the set will mean what mathematical set is I would go with a List. I can easily see a situation when a person says "set" but they mean a multiset. And another pitfall with using a set here is that if the caller screws up and passes multiset to your code your code would run ok and returns silently (no expections of having an illegal arugment) an error result. This result gets passed on and on and couple miles down the road you would start noticing some strange behavior but it would be much harder to track it back to this original place where the error occurred. In comparission if you have a List and the caller passes multiset , even though they are not supposed to, you can notice that much easier because the duplication of the integers would appear somewhere in the output or debugger, or you would not mind that there are some integers multiple times. Ideal would be if your code validates the input and throws IllegalArgumentException. The Set is nice for operations but it possess that risk of an hidden error, that I described.

That much for the discussion about Set since it was brought up.

Naming of variables
I would suggest better names for variables, especially the arguments for the result in the compute method. You name it prevFirstHalf but I think something that says that this is actually the array that will hold the result that you search for would be better. I would go with resultFirstHalf or something like that.

Also the array name a is used often but something like input would be better for understanding the code. Plus since you dont change the input I would include final modifier in front of it. I know it does not prevent you from changing the values of the array but if I read it and see final I immediately think "ok so the input is not being changed or shuffled or anything like that". Connected to that your usage of final in the method I find misleading, because of that fact that I just described. You have final collection but then you fill it so it changes the collection. I know that final prevents you from reassigning the reference but I don't think that should be the core meaning of that.

Just a small point about the algorithm: I see you are counting the difference everything time. But if you are moving the items from one collection to another you know what you are moving so you can just count diff at the beginning and then remember it and add/subtract what ever integer you are moving between the collections.

Idea for speeding up (would have to be investigated): Another point I did not look into too deeply was an idea of starting with the two collections of the desired size produced by random split. It would eliminate the states when you are going through the states when even if the diff was zero the size would not meet the requirement. Then every step you would pick most suitable candidates (most suitable would have to be defined by a heuristic) and you would swap them. On the other hand I don't know if you could simply use a hungry algorithm with the goal of minimizing the diff between the collection by swapping two items every time - you can look into that if you have not before.

\$\endgroup\$
2
\$\begingroup\$

Set is a wrong choice for data representation. Even though the problem statement talks about sets and subsets, they are not sets in the Java sense. Try to run your test against the second example (hint: in the second example 4 appears twice).

Time complexity is indeed exponential, therefore prohibitive.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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