c++ - 获取数组中所有数字组合且无间隙的最快方法

Question

我需要计算数组中每种可能的数字组合的总和(单独的总和，而不是总和)。组合不能跳过数字，因此:

对于 y > x，您需要将 a[x] 和 a[y] 之间的每个数字相加。

对于 n 大小的数组，您有 (n)+(n-1)+(n-2)+...+1 ，因此对于 n = 5，有 15 种组合。

我需要尽快完成，而且空间不是问题。

编辑:我尝试过:

unsigned long long r_all = 0;
std::vector<int> g_seentimes(m);

for(int i = 0; i<n; i++)
    r_all += w[z];
    if(r_all > r){
        r = r_all;
    }
}

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

    unsigned long long r_temp = r_all;

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

        r_temp -= w[n-i];

        if( r_temp > r){
            r = r_temp;
        }
    }

    r_all -= w[y];

    if( r_all > r){
            r = r_all;
    }

}

和

for(int i = 0; i < n; i++){
    unsigned long long r_temp = 0;
    for(int j = 0; j<(n-i); j++){
        r_temp += w[i+j];
        if(r_temp > r){
            r = r_temp;
        }
    }
}
//r is the answer

编辑2: 预期输出是最大可能的数字，但我提供的示例是简单版本，最初如果有两个或多个相同数字的组合，则不会添加其中任何一个的值，因此 {5, 3, 5, 3, 1} = 1，但是 {5, 3, 1} = 9。我已经弄清楚了这部分，只需要尽可能最快的方法来完成所有组合。

编辑3: @Tuan333当被问及组合数量时，我认为展示它会更容易:

X- chosen, x-unchosen
n = 5

XXXXX    XXXXx    XXXxx    XXxxx    Xxxxx
xXXXX    xXXXx    xXXxx    xXxxx
xxXXX    xxXXx    xxXxx
xxxXX    xxxXx
xxxxX

Answer 1

首先创建一个累积部分和的数组。因此，如果您的号码是 a = [1, 2, 3, 4, 5]那么该数组将是 b = [0, 1, 3, 6, 10, 15] 。 (请注意，我在开头包含了空总和，因此第二个数组更大。

现在观察 i 的总和th 至 j a 的第 个元素是 b[j+1] - b[i] 。所以现在你可以做一个双循环。