求所有可能对的总和

Question

我有一个数字数组，我想生成以下项目的总和：

• 选择一个元素并将其与不与该元素相邻的项目相加。

例如：

arr = [2,7,11, 13]

output = [13, 15, 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

Also arr[0] + arr[3]=15

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<Integer> 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<Integer> 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 是数组的大小。

解决这个问题的正确方法是什么。

Answer 1

根据您的解释，您期望输出为 [13, 20, 26]。根据评论，这是一种解决方案。如果可以的话，请优化一下代码。

        public static void main(String[] args) {

        int[] arr = new int[]{2, 7, 11, 13};
        Set<Integer> result = new TreeSet<>();

        int sum = 0;

        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
        }

        for (int i = 0; i < arr.length; i++) {
            if (i == 0) {
                int r = sum - arr[arr.length - 1] - arr[i + 1];
                result.add(r);
            } else if (i == arr.length - 1) {
                int r = sum - arr[i - 2];
                result.add(r);
            } else {
                int r = sum - arr[i + 1] - arr[i - 1];
                result.add(r);
            }
        }
        System.out.println(result);
    }

O/P： [13, 20, 26]