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

@kasavbere-

最近，一位朋友参加了 Google 一份 C++ 编程工作的一场令人痛苦的全天面试。他的经历与你相似。

这启发了他写这篇文章 - 我想你可能会喜欢它：

务实的防御