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]。 (请注意，我在开头包含了空总和，因此第二个数组更大。

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