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