Найти сумму всех возможных пар ⇐ JAVA

[Anonymous]

У меня есть массив чисел, я хочу сгенерировать сумму элементов так, чтобы:

• Выберите элемент и просуммируйте его с элементами, которые не являются соседними. к этому элементу.

Например:

Код: Выделить всё

arr = [2,7,11, 13]

output = [13, 20, 26]

Объяснение:

Код: Выделить всё

Selecting arr[0] and items which are not adjacent to it -> ar[2], ar[3]
sums are arr[0] + arr[2] = 13, arr[0]+arrr[2]+arr[3] = 26

Selecting arr[1] and items which are not adjacent to it -> ar[3]
sums are arr[1] + arr[3] = [20]

So possible sums are [13, 26, 20]
sort this and return as response = [13, 20, 26]

Вот мой код, использующий подход с возвратом:

Код: Выделить всё

import java.util.*;

public class Main {

// Function to generate all possible subsets and calculate their sums
static void generateSubsets(int[] nums, List subsetSums, int index, int currentSum) {
if (index == nums.length) {
subsetSums.add(currentSum);
return;
}

// Include the current element in the subset
generateSubsets(nums, subsetSums, index + 1, currentSum + nums[index]);

// Exclude the current element from the subset
generateSubsets(nums, subsetSums, index + 1, currentSum);
}

public static void main(String[] args) {
int[] nums = {2,7,11, 13}; // Sample array

List subsetSums = new ArrayList();
generateSubsets(nums, subsetSums, 0, 0);

// Sorting the subset sums in ascending order
Collections.sort(subsetSums);

// Printing all possible subset sums
System.out.println(subsetSums);
}
}

Этот код генерирует сумму всех возможных пар как 0 2 7 9 11 13 13 15 18 20 20 22 24 26 31 33 и принимает O(2^n) временная сложность, где n — размер массива.
Каков правильный подход к решению этой проблемы.

Подробнее здесь: https://stackoverflow.com/questions/784 ... ible-pairs