Select X numbers from an array which sum must be N

Question

I have a problem to solve in JavaScript and I am not sure where to start. I will have an array of values.

[1000, 500, 400, 300, 200, 100]

I will be given two numbers

X number of array elements to use.

N Value that the elements must add up to

Sorry but as I don't know where to start, I do not have any attempted code to share.

Any tips on where to start would be greatly appreciated

Edit,

So for example X = 4 N = 1700,

I would want all combinations of 1700 with four elements of the array, all array elelemnts can be used as many times as required

[[1000,500,100,100], [1000,400,200,100],[1000,300,300,100],[ 500,500,500,200],[500,500,400,300],[500,400,400,490]]

No negative numbers allowed and N will always be a sum reachable with X number array elements, with no remainder,

for example X = 5, N = 6900 would never happen,

Provide a theoretical example, like x=3 then n=300 so what will happen after? — Aous Mohammad, Apr 25 '23 at 23:50
I think you want to _Select X elements from the array such that their sum is N_. This is, of course, more interesting if negative numbers are allowed. I bet you could easily do it for X = 2. Then spend some time thinking about how to do it for X = 3. ("to match given value..." is a bad way to say "their sum must be...".) — Wyck, Apr 26 '23 at 00:30
See also: [find all subsets that sum to a particular value](https://stackoverflow.com/questions/18305843/find-all-subsets-that-sum-to-a-particular-value) — Wyck, Apr 26 '23 at 00:35
https://stackoverflow.com/questions/4355955/subset-sum-algorithm (not identical to this b/c the linked problem doesn't fix the number of elements) — Dave, Apr 26 '23 at 12:29

score 1 · Accepted Answer · answered Apr 26 '23 at 16:06

We can write a fairly straightforward recursion that on every step reduces some combination of the list of numbers, the count of numbers remaining, and the total sought.

const combine = (ns, count, total) =>
  count == 0
    ? total === 0 ? [[]] : []
  : ns .length < 1 || total < 0 || count < 0
    ? []
  : combine (ns, count - 1, total - ns [0]) .map (g => [ns [0], ...g]) 
      .concat (combine (ns .slice (1), count, total))

const parts = [1000, 500, 400, 300, 200, 100]

console .log (combine (parts, 4, 1700))

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

There are two base cases. First, if the count is exactly zero, then we check the total: if it's zero, then we return one empty array, and if it's not, we return no values. Second, if our array of options is empty or if either our total or the remaining count are negative, then we return no values.

Otherwise, we concatenate two results. In the first one, we use the first entry, combining it with every result from recurring on the same array of values, a decremented count, and the difference between the total and that first entry. In the second one, we skip the first value and recur with the remaining values, the same count, and the same total.

The name "combine" is too generic, but at the moment I can't come up with a better one.

Select X numbers from an array which sum must be N

1 Answers1