Как найти суммирование умножения элементов во всех возможных подмножествах без повторения?

Question

У меня был этот вопрос в конкурсе, я пытался ответить на него с помощью этого кода (на Java, но вы действительно можете использовать любой из поддерживаемых языков, сайт конкурса указан внизу):

static long calcMultisSums(int[] arr)
{
    int sum=0, n=arr.length;
    for(int i=0;i<n;i++)
        sum+=arr[i];

    int mult=0;

   for(int i=0;i<n;i++){
       for(int b=i+1;b<n;b++)
           mult+=arr[b]*arr[i];
   }
   int mult2=0;
    if(n>2){
        mult2=1;
        for(int value : arr) {
            mult2 *= value;
        }      
    }


    return mult+sum+mult2;
}

Он работает для массивов, содержащих менее 4 элементов, но всякий раз, когда он получает 4 или более элементов, он в итоге дает неправильный ответ, который, очевидно, потому что он рассчитывает умножение всех элементов, суммирование всех элементов, а затемумножает каждый элемент перед каждым, если количество элементов в arr> 3. Это, очевидно, плохое решение проблемы, и я уверен, что должна быть лучшая реализация для решения.

Вот конкурс на вопрос , где вы можете прочитать проблему и проверить свои ответы.(Задача № 6, задача суммирования)

Answer 1

Наивный подход:

1. Создание статической переменной sum = 0 поиск всех подмножеств массива (в вашем примере это называется powerset): Как найти все подмножества массива в java?
2. рассчитывать продукт для каждого набора
3. добавить его к sum

и лучшее решение здесь: Сумма произведений всехвозможные подмножества массива