java - 给定一组 n 个整数，返回总和为 0 的 k 个元素的所有子集

Question

给定一个未排序的 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)

但随后她提出了以下要求:

• 必须在答案中使用 hashmap 以降低时间复杂度
• 必须绝对——绝对——为一般情况提供时间复杂度
• 当 k=6 时提示，O(n^3)

她对时间复杂度最感兴趣。

有人知道满足新约束的解决方案吗？

---

编辑:

据推测，在正确的解决方案中， map 将存储输入的元素，然后 map 将用作查找表，就像 k=2 的情况一样。

当子集的大小为 2(即 k=2)时，答案很简单:遍历并将所有元素加载到 map 中。然后再次循环输入，这次在 map 中搜索 sum - input[i]，其中 i 是从 0 到 n-1 的索引，这就是答案。假设这个简单的情况可以扩展到 k 是任何东西的地方。

Answer 1

既然没有其他人尝试过，我不妨至少提供一个部分解决方案。正如我在之前的评论中指出的那样，这个问题是 subset sum problem 的变体。在开发此解决方案时，我非常依赖记录在案的解决该问题的方法。

我们正在尝试编写一个函数 subsetsWithSum(A, k, s) 来计算 A 的所有 k 长度子集，这些子集总和为 s。这个问题以两种方式适用于递归解决方案:

1. subsetsWithSum(x₁ ... x_n, k, s) 的解可以通过计算 subsetsWithSum(x₂ ... x_n, k, s) 并添加包含 x₁ 的所有有效子集(如果有的话)；和
2. 所有包含元素 x_i 的有效子集都可以通过计算 subsetsWithSum(A - x_i, k-1, s-x_i>) 并将 x_i 添加到结果的每个子集(如果有的话)。

递归的基本情况发生在 k 为 1 时，在这种情况下，subsetsWithSum(A, 1, s) 的解是所有单个元素子集的集合，其中该元素等于 s。

所以第一个解决方案是

/**
 * 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;
}

现在，请注意，此解决方案通常会使用与之前调用时使用的相同参数集调用 subsetsWithSum(...)。因此，subsetsWithSum 只是乞求成为 memoized .

为了记住函数，我将参数 k、s 和 o 放入一个三元素列表中，这将是从这些参数到之前计算的结果(如果有的话)的映射的关键:

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

要使用 subsetsWithSum 函数计算所有总和为零的 k 长度子集，可以使用以下函数:

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

遗憾的是，我的复杂度计算技巧有点(读作:非常)生疏，所以希望其他人可以帮助我们计算这个解决方案的时间复杂度，但这应该是对蛮力方法的改进。

编辑:为了清楚起见，请注意上面的第一个解决方案在时间复杂度上应该等同于蛮力方法。内存函数在很多情况下应该会有帮助，但在最坏的情况下，缓存永远不会包含有用的结果，时间复杂度将与第一个解决方案相同。另请注意，子集和问题是 NP-complete这意味着任何解决方案都具有指数时间复杂度。 结束编辑。

为了完整性，我测试了这个:

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

它打印了:

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