given a set of n integers, return all subsets of k elements that sum to 0

Question

given a unsorted set of n integers, return all subsets of size k (i.e. each set has k unique elements) that sum to 0.

So I gave the interviewer the following solution ( which I studied on GeekViewpoint). No extra space used, everything is done in place, etc. But of course the cost is a high time complexity of O(n^k) where k=tuple in the solution.

public void zeroSumTripplets(int[] A, int tuple, int sum) {
  int[] index = new int[tuple];
  for (int i = 0; i < tuple; i++)
    index[i] = i;
  int total = combinationSize(A.length, tuple);
  for (int i = 0; i < total; i++) {
    if (0 != i)
      nextCombination(index, A.length, tuple);
    printMatch(A, Arrays.copyOf(index, tuple), sum);
  }// for
}// zeroSumTripplets(int[], int, int)

private void printMatch(int[] A, int[] ndx, int sum) {
  int calc = 0;
  for (int i = 0; i < ndx.length; i++)
    calc += A[ndx[i]];
  if (calc == sum) {
    Integer[] t = new Integer[ndx.length];
    for (int i = 0; i < ndx.length; i++)
      t[i] = A[ndx[i]];
    System.out.println(Arrays.toString(t));
  }// if
}// printMatch(int[], int[], int)

But then she imposed the following requirements:

• must use hashmap in answer so to reduce time complexity
• Must absolutely -- ABSOLUTELY -- provide time complexity for general case
• hint when k=6, O(n^3)

She was more interested in time-complexity more than anything else.

Does anyone know a solution that would satisfy the new constraints?

---

EDIT:

Supposedly, in the correct solution, the map is to store the elements of the input and the map is then to be used as a look up table just as in the case for k=2.

When the size of the subset is 2 (i.e. k=2), the answer is trivial: loop through and load all the elements into a map. Then loop through the inputs again this time searching the map for sum - input[i] where i is the index from 0 to n-1, which would then be the answers. Supposedly this trivial case can be extended to where k is anything.

Answer 1

Since no-one else has made an attempt, I might as well throw in at least a partial solution. As I pointed out in an earlier comment, this problem is a variant of the subset sum problem and I have relied heavily on documented approaches to that problem in developing this solution.

We're trying to write a function subsetsWithSum(A, k, s) that computes all the k-length subsets of A that sum to s. This problem lends itself to a recursive solution in two ways:

1. The solution of subsetsWithSum(x₁ ... x_n, k, s) can be found by computing subsetsWithSum(x₂ ... x_n, k, s) and adding all the valid subsets (if any) that include x₁; and
2. All the valid subsets that include element x_i can be found by computing subsetsWithSum(A - x_i, k-1, s-x_i) and adding x_i to each subset (if any) that results.

The base case for the recursion occurs when k is 1, in which case the solution to subsetsWithSum(A, 1, s) is the set of all single element subsets where that element is equal to s.

So a first stab at a solution would be

/**
 * Return all k-length subsets of A starting at offset o that sum to s.
 * @param A - an unordered list of integers.
 * @param k - the length of the subsets to find.
 * @param s - the sum of the subsets to find.
 * @param o - the offset in A at which to search.
 * @return A list of k-length subsets of A that sum to s.
 */
public static List<List<Integer>> subsetsWithSum(
        List<Integer> A,
        int k,
        int s,
        int o)
{
    List<List<Integer>> results = new LinkedList<List<Integer>>();

    if (k == 1)
    {
        if (A.get(o) == s)
            results.add(Arrays.asList(o));
    }
    else
    {
        for (List<Integer> sub : subsetsWithSum(A, k-1, s-A.get(o), o+1))
        {
            List<Integer> newSub = new LinkedList<Integer>(sub);
            newSub.add(0, o);
            results.add(0, newSub);
        }
    }

    if (o < A.size() - k)
        results.addAll(subsetsWithSum(A, k, s, o+1));

    return results;
}

Now, notice that this solution will often call subsetsWithSum(...) with the same set of arguments that it has been called with before. Hence, subsetsWithSum is just begging to be memoized.

To memoize the function, I've put the arguments k, s and o into a three element list which will be the key to a map from these arguments to a result computed earlier (if there is one):

public static List<List<Integer>> subsetsWithSum(
        List<Integer> A,
        List<Integer> args,
        Map<List<Integer>, List<List<Integer>>> cache)
{
    if (cache.containsKey(args))
        return cache.get(args);

    int k = args.get(0), s = args.get(1), o = args.get(2);
    List<List<Integer>> results = new LinkedList<List<Integer>>();

    if (k == 1)
    {
        if (A.get(o) == s)
            results.add(Arrays.asList(o));
    }
    else
    {
        List<Integer> newArgs = Arrays.asList(k-1, s-A.get(o), o+1);

        for (List<Integer> sub : subsetsWithSum(A, newArgs, cache))
        {
            List<Integer> newSub = new LinkedList<Integer>(sub);
            newSub.add(0, o);
            results.add(0, newSub);
        }
    }

    if (o < A.size() - k)
        results.addAll(subsetsWithSum(A, Arrays.asList(k, s, o+1), cache));

    cache.put(args, results);
    return results;
}

To use the subsetsWithSum function to compute all the k-length subsets that sum to zero, one can use the following function:

public static List<List<Integer>> subsetsWithZeroSum(List<Integer> A, int k)
{
    Map<List<Integer>, List<List<Integer>>> cache =
            new HashMap<List<Integer>, List<List<Integer>>> ();
    return subsetsWithSum(A, Arrays.asList(k, 0, 0), cache);
}

Regrettably my complexity calculating skills are a bit (read: very) rusty, so hopefully someone else can help us compute the time complexity of this solution, but it should be an improvement on the brute-force approach.

Edit: Just for clarity, note that the first solution above should be equivalent in time complexity to a brute-force approach. Memoizing the function should help in many cases, but in the worst case the cache will never contain a useful result and the time complexity will then be the same as the first solution. Note also that the subset-sum problem is NP-complete meaning that any solution has an exponential time complexity. End Edit.

Just for completeness, I tested this with:

public static void main(String[] args) {
    List<Integer> data = Arrays.asList(9, 1, -3, -7, 5, -11);

    for (List<Integer> sub : subsetsWithZeroSum(data, 4))
    {
        for (int i : sub)
        {
            System.out.print(data.get(i));
            System.out.print(" ");
        }

        System.out.println();
    }
}

and it printed:

9 -3 5 -11
9 1 -3 -7

Answer 2

I think your answer was very close to what they were looking for, but you can improve the complexity by noticing that any subset of size k can be thought of as two subsets of size k/2. So instead of finding all subsets of size k (which takes O(n^k) assuming k is small), use your code to find all subsets of size k/2, and put each subset in a hashtable, with its sum as the key.

Then iterate through each subset of size k/2 with a positive sum (call the sum S) and check the hashtable for a subset whose sum is -S. If there is one then the combination of the two subsets of size k/2 is a subset of size k whose sum is zero.

So in the case of k=6 that they gave, you would find all subsets of size 3 and compute their sums (this will take O(n^3) time). Then checking the hashtable will take O(1) time for each subset, so the total time is O(n^3). In general this approach will take O(n^(k/2)) assuming k is small, and you can generalize it for odd values of k by taking subsets of size floor(k/2) and floor(k/2)+1.