数组所有可能子集的乘积之和

Question

我已经编写了一段代码来查找数组的所有可能子集的乘积之和。我得到了预期的输出，但我无法使它快速到足以通过与时间相关的测试用例。 有人可以帮我优化我的代码以提高速度吗？ 第一个输入（testCases）是测试用例的数量。根据测试用例的数量，我们将拥有数组的大小（size）和数组元素（set）。

例如，有效的输入如下：

1
3
2 3 5

其中：

1 是测试用例的数量。 3 是测试集的大小，2 3 5 是输入集的元素。

期望输出为：

71

以上输出的计算方法如下：

    {2}, {3}, {5}, {2, 3}, {3, 5}, {2, 5}, {2, 3, 5}

=>   2    3    5      6      15      10        30

=>   2 + 3 + 5 + 6 + 15 + 10 + 30

=>   71

---

import java.util.Scanner;

public class Test {
    static int printSubsets(int set[]) {
        int n = set.length;
        int b = 0;

        for (int i = 0; i < (1 << n); i++) {
            int a = 1;
            for (int j = 0; j < n; j++){

                if ((i & (1 << j)) > 0) {

                    a *= set[j];
                }}

            b += a;
        }
        return b;
    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int testCases = scanner.nextInt();

        for (int i = 0; i < testCases; i++) {
            int size = scanner.nextInt();
            int set[] = new int[size];
            for (int j = 0; j < set.length; j++) {
                set[j] = scanner.nextInt();
            }

            int c = printSubsets(set);
            System.out.println((c - 1));

        }
        scanner.close();
    }
}

- Joginder Pawan

---

你能否明确你的问题？如果我理解正确的话，你的算法应该计算 (2 * 3) + (2 * 5) + (2 * 3 * 5) + (3 * 5) = 61。 - Turing85

每个单独的元素也是有效的子集。你需要将 2 + 3 + 5 加到 61 上。这样你就得到了 71。 - anacron

你想要优化你的代码，我猜是吧？“足够快以通过与时间相关的测试用例。” - 7663233

Joginder，你能加上你想要达到的时间复杂度吗？ - anacron

@anacron，在这个问题中，我被要求每个输入的时间限制为10.0秒。但是我只能达到20.0秒。 - Joginder Pawan

Answer 1

你需要用一点数学。假设你有三个值，就像你的例子一样，但我们称它们为 A、B 和 C。

为了得到乘积总和，您需要计算：

Result3 = A + B + C + A*B + A*C + B*C + A*B*C
        = A + B + A*B + (1 + A + B + A*B) * C

现在，如果我们先计算A + B + A*B，并将其称为Result2，那么你会得到：

Result2 = A + B + A*B
Result3 = Result2 + (1 + Result2) * C

我们重申一遍，如下：

Result2 = A + (1 + A) * B
Result1 = A
Result2 = Result1 + (1 + Result1) * B

你能看到这个模式吗？我们用四个值来说明：

Result4 = A + B + C + D + A*B + A*C + A*D + B*C + B*D + C*D
        + A*B*C + A*B*D + A*C*D + B*C*D + A*B*C*D
        =      A + B + C + A*B + A*C + B*C + A*B*C
        + (1 + A + B + C + A*B + A*C + B*C + A*B*C) * D
        = Result3 + (1 + Result3) * D

摘要：

Result1 = A
Result2 = Result1 + (1 + Result1) * B
Result3 = Result2 + (1 + Result2) * C
Result4 = Result3 + (1 + Result3) * D

作为代码，它的样子是这样的：

private static long sumProduct(int... input) {
    long result = 0;
    for (int value : input)
        result += (result + 1) * value;
    return result;
}

只需要一次迭代，因此时间复杂度为O(n)。

测试

System.out.println(sumProduct(2, 3));
System.out.println(sumProduct(2, 3, 5));
System.out.println(sumProduct(2, 3, 5, 7));

输出

11
71
575

更新

可以使用Java 8的流和Lambda表达式来编写代码，通过使用IntStream.of(int...)或Arrays.stream(int[])（它们的作用相同）。

// Using IntStream with result as int
private static int sumProduct(int... input) {
    return IntStream.of(input).reduce((a, b) -> a + (1 + a) * b).getAsInt();
}

// Using Arrays with result as long
private static long sumProduct(int... input) {
    return Arrays.stream(input)
                 .asLongStream()
                 .reduce((a, b) -> a + (1 + a) * b)
                 .getAsLong();
}

- Andreas