找到子集和，得到顶部的z元素

Question

我有一个数字数组，现在我想找到所有可能的子集和，并得到其中的顶部z元素。

例子：

Input : arr[] = {2, 4, 5}, z = 3
SubsetSums : 0 2 4 5 6 7 9 11
output : Top z=3 elements = 11,9,7

这是我的代码：

static List<Long> subsetSums(int arr[], int n)
    {
 
        // There are total 2^n subsets
        int total = 1 << n;
        List<Long> list = new ArrayList<>(); 
        // Consider all numbers from 0 to 2^n - 1
        for (int i = 0; i < total; i++) {
            int sum = 0;
 
            // Consider binary representation of
            // current i to decide which elements
            // to pick.
            for (int j = 0; j < n; j++)
                if ((i & (1 << j)) != 0)
                    sum += arr[j];
 
            // Print sum of picked elements.
            System.out.print(sum + " ");
            list.add(sum);
        }
        list.sort((a,b) -> b.compareTo(a));
        List<Long> response = new ArrayList<>();
        for(int i=0; i<k && i<list.size(); i++) {
           response.add(list.get(i));  
        }
        return response;
    }

我从[this][1]帖子中获取了部分代码。

这个程序的时间复杂度是O（n*2^2）

我在一次Hackerrank考试中使用过这个，但在15个测试用例中，只有7个通过了测试，其余的都超时了，因为输入大小n可能非常大。

如何以较低的时间复杂度解决这个问题？[1]: https://www.geeksforgeeks.org/print-sums-subsets-given-set/

Answer 1

如果首先对输入数组进行排序，则不必计算所有这些和：

• 最大的总和是所有值的总和

当z比n^2小得多时，这将大大加快解决方案的速度。