Find all combination of values which total equals N (javascript)

Question

I am calculating some chemistry for which i need combination of values which total equals N number. I have following array for which each values can't be more than X

Array :
Index | Max Value
0 | 370
1 | 185
2 | 740
3 | 277.5
4 | 277.5
5 | 1850
6 | 925
7 | 1850

i need a function which will calculate all possible combination of values from each array index which total equals 1850.

Eg.
0 | 77.00
1 | 700.00
2 | 50.00
3 | 300.00
4 | 700.00
5 | 15.00
6 | 7.00
7 | 1.00
which Total = 1850

Thanks in advance for your help

Does this answer your question? [Return all subsets whose sum is a given value (subset sum problem)](https://stackoverflow.com/questions/53659151/return-all-subsets-whose-sum-is-a-given-value-subset-sum-problem) — aRvi, Sep 20 '20 at 11:40
@aRvi above question is a static array which will be passed, i want any combination of values which does not exceeds max value — Nitin Muchhadiya, Sep 20 '20 at 11:49
_"...can't be more than X ..."_ - but can be zero or negative? — Tibebes. M, Sep 20 '20 at 12:56

Tibebes. M · Answer 1 · 2020-09-20T14:15:02.893

Here is one approach.

sort the array in ascending order (to make the distribution a bit fair - since we will be looping for first to end sequentially and pick numbers, the large numbers might shadow the smaller numbers for having a chance)
prepare a new array for result (initialize with 0)
for each entry in the sorted array, we will take some random value until (the the total sum is reached) - we are decreasing some counter variable in this example to track that (pointsLeft). Add the randomly picked number to the result array at the specified index (the result array index should follow the original array's order - not the sorted one)
if there is not pointsLeft, it means the items in the result array is equal to the desired sum. So we just return the result array.

const testArray = [
  370,
  185,
  740,
  277.5,
  277.5,
  1850,
  925,
  1850,
]

function getRandomInt(min, max) {
  min = Math.ceil(min);
  max = Math.floor(max);
  return Math.floor(Math.random() * (max - min + 1)) + min;
}

function getCombination(values, pointsLeft) {
  let sorted = values.map((x, i) => {
    return [x, i]
  }).sort((a, b) => a[0] - b[0]); // sorted from small -> large - keeping the original index

  const result = new Array(values.length).fill(0)

  while (pointsLeft > 0) {
    for (const [_, [value, original_index]] of sorted.entries()) {
      someRandomValueToSubtract = getRandomInt(1, value / 2)
      if (pointsLeft - someRandomValueToSubtract < 0) continue
      pointsLeft -= someRandomValueToSubtract
      result[original_index] += someRandomValueToSubtract
    }
  }

  return result
}

const x = getCombination(testArray, 1850)

console.log("ITEMS:", x)

console.log("SUM:", x.reduce(function(a, b) {
  return a + b;
}, 0))

.as-console-wrapper { max-height: 100% !important; top: 0; }

@ Tibebes. M great solution, instead of assuming some random numbers, can we get all combinations which sum to 1850? — Nitin Muchhadiya, Sep 20 '20 at 14:32
@NitinMuchhadiya Oh, I think calculating all the combinations with such max-values would be highly memory intensive task (and impossible if floating numbers are considered - infinite possibilities). I'll update the answer if I find an optimized solution though. — Tibebes. M, Sep 20 '20 at 15:12
@NitinMuchhadiya, note that there could be potentially `1.2304101e+22` amount of checks if we were to check all combinations (assuming only integer values and your input array) — Tibebes. M, Sep 20 '20 at 16:16
that would work for me, hope so there will be no memory issue using this — Nitin Muchhadiya, Sep 21 '20 at 17:46
@ Tibebes. M Thanks a lot, i have made solution from the random numbers that you posted above. — Nitin Muchhadiya, Sep 27 '20 at 06:34

Find all combination of values which total equals N (javascript)

1 Answers1