Same average subset

Problem

Given an integer array find all subsets having equal average.

Solution

We will use a structure to store the count and sum of a subset. So that if we add any element to an existing array we can find the average in O(1) time. After processing till ith index we memoize all the subsets possible with the elements from 0 to i. Now for i+1 th number we add this number to all previous subsets and start a subset with the number itself. As we maintain the sum and count for all the subsets, we can calculate the average at the same complexity as we add the numbers to the old subsets. Then we create a hashmap where key is the average and value is a list of subsets. We add all the subsets in this hash map. Then we iterate over all the keys of the hash map and wherever the value contains a list having more than one element we print those subsets corresponding to that average. This has a complexity of O(n*2^n). Because there are total 2^n possible subsets from n numbers.

Code

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class SameAverageSubset
{
 public static void main(String[] args)
 {
  int[] input =
  { 4, 1, 7, 8, 3, 5 };
  ArrayList table = new ArrayList();
  HashMap < Double, List> hashMap = new HashMap < Double, List>();
  for (int i = 0; i < input.length; ++i)
  {
   int num = input[i];
   ArrayList tempTable = new ArrayList();
   for (SumCountPair j : table)
   {
    SumCountPair temp = j.clone();
    temp.add(num);
    tempTable.add(temp);
   }
   table.addAll(tempTable);
   SumCountPair sumCountPair = new SumCountPair();
   sumCountPair.add(num);
   table.add(sumCountPair);
  }
  for (SumCountPair j : table)
  {
   List temp = hashMap.get(j.average());
   if (temp != null)
   {
    temp.add(j);
   } else
   {
    temp = new ArrayList();
    temp.add(j);
   }
   hashMap.put(j.average(), temp);
  }
  for (Double average : hashMap.keySet())
  {
   List list = hashMap.get(average);
   if (list.size() == 1)
    continue;
   System.out.print(average + " ");
   for (SumCountPair sumCountPair : list)
    System.out.print(sumCountPair + ", ");
   System.out.println();
  }

 }

}

class SumCountPair
{
 int sum;
 int count;
 ArrayList array;

 public SumCountPair()
 {
  this(0, 0);
 }

 public SumCountPair(int sum, int count)
 {
  this(sum, count, new ArrayList());
 }

 public SumCountPair(int sum, int count, ArrayList array)
 {
  this.sum = sum;
  this.count = count;
  this.array = (ArrayList) array.clone();
 }

 @Override
 public SumCountPair clone()
 {
  return new SumCountPair(sum, count, array);
 }

 public void add(int num)
 {
  sum += num;
  count++;
  array.add(num);
 }

 public double average()
 {
  return (double) sum / count;
 }

 public String toString()
 {
  return array.toString();
 }
}

Index