0

很简单的问题：

给定一个数组，找出总和为 k 的所有子集

我正在尝试在 Java 中执行此操作，并且似乎找到了在 O(n^2) 时间内解决它的解决方案。这个解决方案是正确的 O(n^2) 实现吗？

      @Test
    public void testFindAllSubsets() {
        int[] array = {4,6,1,6,2,1,7};
        int k=7;
                 // here the algorithm starts
        for(int i = 0; i < array.length;i++){
            // now work backwords
            int sum = array[i];
            List<Integer> subset = new ArrayList<Integer>();
            subset.add(array[i]);
            for(int j = array.length -1; j > i && sum < k; j--){
                int newSum = sum + array[j];
                                    // if the sum is greater, than ditch this subset
                if(newSum <= k){
                    subset.add(array[j]);
                    sum = newSum;
                }
            }
            // we won't always find a subset, but if we do print it out
            if(sum == k){
                System.out.print("{");
                System.out.print(subset.get(0));
                for(int l = 1; l < subset.size(); l++){
                    System.out.print(","+subset.get(l));
                }
                System.out.print("}");
                System.out.println();
            }
        }
    }

我已经尝试了各种示例，但没有发现任何似乎破坏它的示例。但是，当我在网上搜索时，这似乎不是该问题的常见解决方案，并且许多解决方案声称这个问题是 O(2^n)。

PS 这不是一个家庭作业问题，我是一名程序员，我的工作是在 Java 中研究我的 Comp Sci 基础知识。谢谢！

4

2 回答 2

2

不，这是不正确的。举这个简单的例子

你的数组是 4,6,1,2,3,1 并且目标总和是 7 然后在你的逻辑中它只会找到 (4,3) (6,1) (1,2,3,1) 你的代码会错过(4,2,1), (4,3)。

我会参考通过wiki

于 2013-08-10T04:17:35.267 回答
1

一个优雅的解决方案是将一个子集简单地视为每个成员回答“我在还是不在？”这个问题。所以基本上每个人都可以回答是/否，所以你有 2 N个子集（包括空子集）。最自然的编码方式是递归每个元素并执行以下操作之一：

  1. 选择
  2. 跳过它

因此，时间复杂度为 O(2 N ) 仅仅是因为在最坏的情况下您可能有很多答案。

于 2013-08-10T07:49:00.843 回答