Javascript combinations sum

Question

I am trying to realize a certain mathematical combination into Javascript but can find the best way to do it.

What I am trying to achieve is finding the sum of combinations(consisting of 3 elements) out of N.

For example, how can I find sum of all possible combinations consisting of 3 elements out of 5?

Manually it looks like this:

Selections: A,B,C,D,E - all of them are numbers

All possible 3 out of 5 combos are as follows:

ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE

ABC means A * B * C

The sum of combos in its simplified form will look like this:

AB(C+D+E) + AC(D+E) + ADE + BC(D+E) + BDE + CDE.

I have tried the following code but it did not work out:

function calc(arr) {
  var total = 0;
  for (let i = 0; i < arr.length; i++) {
    let sum = 0;
    for (let j = i + 1; j < arr.length; j++) {
      sum += arr[j] + arr[j + 1] + arr[j + 2];
    }
    total += sum * arr[i] + arr[i + 1] + arr[i + 2];
  }
  return total;
}

var arr = [2, 3, 4, 5, 6];
console.log(calc(arr));

You have asked the [same question](https://stackoverflow.com/questions/63317841/) yesterday and it was closed. The duplicates mention how to create subsets of size k from an array of length n. Once you find the subsets, multiply the items within the subset and sum all the subsets. You have still not made an effort to implement the combinations part in your code. — adiga, Aug 09 '20 at 07:15

Declan McKelvey-Hembree · Answer 1 · 2020-08-09T07:21:32.827

function calc(arr){
    var total = 0;
    //first iterate over first possible coefficient
    for(var i = 0; i < arr.length - 2; i++){
    var coeff1 = arr[i];
    //then iterate over second possible coefficient
    for(var j = i + 1; j < arr.length - 1; j++){
      var coeff2 = arr[j];
      var parentheticalSum = 0;
      //all other values are summed and then made the third coefficient
      for(var k = j + 1; k < arr.length; k++){
        parentheticalSum += arr[k];
      }
      total += coeff1 * coeff2 * parentheticalSum;
    }
  }
  return total;
}

console.log(calc([1,2,3,4,5])); //outputs 225
// 1*2*(3+4+5) + 1*3*(4+5) + 1*4*(5) + 2*3*(4+5) + 2*4*(5) + 3*4*(5) = 225

The above does work, but it can definitely be optimized. The one that jumps out to me is that we're doing a lot of repeat sums, and we should replace the third loop with a single reversed cumulative sum table.

Here's that optimization:

function calc(arr){
  var reverseCumSumLookup = [];
  var reverseCumSum = 0;
  for(var rev = arr.length - 1; rev >= 0; rev--){
    reverseCumSum += arr[rev];
    reverseCumSumLookup[rev] = reverseCumSum;
  }
  var total = 0;
  for(var i = 0; i < arr.length - 2; i++){
    var coeff1 = arr[i];
    for(var j = i + 1; j < arr.length - 1; j++){
      var coeff2 = arr[j];
      var parentheticalSum = reverseCumSumLookup[j+1];
      total += coeff1 * coeff2 * parentheticalSum;
    }
  }
  return total;
}

This improves complexity from n^3 to n^2. Is it possible to do better than this?

Javascript combinations sum

1 Answers1