给定一组n个整数，返回总和为0的k个元素的所有子集 [英] given a set of n integers, return all subsets of k elements that sum to 0

查看：112
本文介绍了给定一组n个整数，返回总和为0的k个元素的所有子集的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

给出一组未排序的 n 整数，返回大小为k的所有子集（即每组具有k个唯一元素），总和为0.

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.

所以我给了面试官以下解决方案（我在 GeekViewpoint 上学习过） 。没有使用额外的空间，一切都已完成，等等。当然，成本是O（n ^ k）的高时间复杂度，其中 k =元组在解决方案中。

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:


  • 必须在回答时使用hashmap以减少时间复杂度

  • 必须绝对 - 绝对 - 为一般情况提供时间复杂性

  • 提示当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?

编辑：

据说，在正确的解决方案中，地图将存储输入的元素，然后地图将用作查找表，就像 k = 2 。

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.

当子集的大小为2（即 k = 2 ）时，答案是微不足道的：循环并将所有元素加载到地图中。然后再次遍历输入，这次在地图上搜索 sum - input [i]其中i是从0到n-1 的索引，这将是答案。据说这个简单的案例可以扩展到 k 是什么。

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.

推荐答案

由于没有其他人做过尝试，我不妨投入至少部分解决方案。正如我在之前的评论中指出的那样，这个问题是子集和问题的一个变体，我在开发此解决方案时，我们非常依赖于记录在案的方法。

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.

我们正在尝试编写一个函数 subsetsWithSum（A，k，s ）计算总和为s的A的所有k长度子集。这个问题有两个方面的递归解决方案：

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. subsetsWithSum的解决方案（x 1 .. .x n ，k，s）可以通过计算subsetsWithSum（x 2 ... x n ，k，s）并添加来找到包含x 1 的所有有效子集（如果有）;和

  2. 通过计算subsetsWithSum（A - x i ，k-1）可以找到包含元素x i 的所有有效子集，sx i ）并将x i 添加到每个子集（如果有的话）中。

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

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

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.

因此首先尝试解决方案

/**
 * 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 。

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.

为了记住这个函数，我把参数k，s和o放到一个三元素列表中，这个列表是从这些参数到先前计算的结果（如果有的话）的映射的关键：

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

使用subsetsWithSum函数计算求和的所有k长度子集零，可以使用以下函数：

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.

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

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

并打印出来：

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

这篇关于给定一组n个整数，返回总和为0的k个元素的所有子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文
相关文章
Java开发最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆