arrays - 如何找到数组中 N 个元素的所有可能和？

Question

我正在寻找有关如何找到 N 个元素的所有可能和的建议。例如，我有一个数组

int []arr={91,58,89,87,25,65,21};

对于某些int n=3;

我需要找到这个数组中 3 个元素的所有可能和。一开始，这对我来说看起来很容易，因为我可以找到大小为 3 的子数组的所有总和，但我不确定大小为 3 的子序列。我在Google上发现了类似的问题，解决方案是使用递归。我不确定我是否真的了解如何根据我的条件解决这个问题，希望您能给我一个建议和例子，以便我可以解决这个问题!我不确定我的初始代码是否需要，因为它是线性工作的。

提前谢谢您。

Answer 1

我有一个针对可变长度子序列的解决方案。Java代码:

public static void main(String[] args) {
    int[] arr = {91, 58, 89, 87, 25, 65, 21};
    int n = 3;

    sum(arr, 0, n, 0);
}

public static void sum(int[] arr, int startIdx, int deep, int currSum) {
    if (deep == 1) {
        for (int i = startIdx; i < arr.length; i++)
            System.out.println(currSum + arr[i]);
    } else {
        for (int i = startIdx; i < arr.length; i++)
            sum(arr, i + 1, deep - 1, currSum + arr[i]);
    }
}

UPD:如果您需要以列表形式获取结果，您可以使用以下变体:

public static void main(String[] args) {
    int[] arr = {91, 58, 89, 87, 25, 65, 21};
    int n = 3;

    List<Integer> sums = sum(arr, n, 0);
    System.out.println(sums);
}

public static List<Integer> sum(int[] arr, int deep, int currSum) {
    List<Integer> list = new ArrayList<>();
    if (deep == 1) {
        for (int value : arr) list.add(currSum + value);
    } else {
        for (int i = 0; i < arr.length; i++)
            list.addAll(sum(Arrays.copyOfRange(arr, i + 1, arr.length), deep - 1, currSum + arr[i]));
    }
    return list;
}