задан набор из n целых чисел, вернуть все подмножества из k элементов, сумма которых равна 0

учитывая несортированный набор из nцелых чисел, вернуть все подмножества размера k (т. е. каждый набор имеет k уникальные элементы ), сумма которых равна 0.

Итак, я дал интервьюеру следующее решение (, которое я изучил на GeekViewpoint). Не используется лишнее пространство, все делается на месте и т. д. Но, конечно, цена — это высокая временная сложность O (n^k ), где k=tupleв решении.

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)

Но затем она выдвинула следующие требования:

• должна использовать хэш-карту в ответе, чтобы уменьшить временную сложность
• Обязательно --АБСОЛЮТНО --обеспечить временную сложность для общего случая
• подсказка, когда k=6, O (n^3)

Она больше всего интересовалась временной -сложностью.

Кто-нибудь знает решение, удовлетворяющее новым ограничениям?

РЕДАКТИРОВАТЬ:

Предположительно, в правильном решении карта должна хранить элементы ввода, а затем карта должна использоваться в качестве таблицы поиска, как и в случае k=2.

Когда размер подмножества равен 2 (т.е.k=2), ответ тривиален :выполнить цикл и загрузить все элементы в карту. Затем снова прокрутите входные данные, на этот раз ища на карте sum - input[i] where i is the index from 0 to n-1, которые затем будут ответами. Предположительно, этот тривиальный случай можно распространить на случай, когда k— что угодно.