Any combination of additions of a specified number set to reach a specific target value

Question

I am looking for a way to get all possible combination of numbers to reach a specified target value. The values of the number set can repeat.

For example:
Number set is 4, 5, 6, 7, 8
The value that I want to reach is 16.

So as result I would like to have something like:

4+4+4+4  
4+4+8  
5+5+6  
...

Any solutions which I've found are only without repeatitions like here:
Efficient algorithm to find a combination, which summation is equal to a known number, in a set of number

Thanks in advance!

you could simply artificially inflate the inputs (i.e. when adding `n`, add `X/n` extra copies of `n`), and use the versions you've already found? not ideal, but it would work — Marc Gravell, Mar 29 '18 at 08:48

MBo · Accepted Answer · 2018-03-29T09:06:01.243

You can use the same recursive approach too. But don't remove used items from the set of possible items. If you want to distinguish between a+b+a and a+a+b variants - traverse all set, if not - only items from the current position.

function Partitions(Sum, A[], CurIdx, Result)
  if Sum = 0
     output Result
  //all variants with permutations
  for i = 0 to A.Length - 1
     if A[i] <= Sum
        Partitions(Sum - A[i], A[], i, Result + A[i])

  //variants without permutations
  for i = CurIdx to A.Length - 1
     if A[i] <= Sum
        Partitions(Sum - A[i], A[], i, Result + A[i])

  // you don't need this, just for record:  
  //variant without repeats essentially does the next:
        Partitions(Sum - A[i], A[].Remove i-th item, i, Result + A[i])

   or (note  i+1 start point for the next recursion level)

  for i = CurIdx to A.Length - 1
     if A[i] <= Sum
        Partitions(Sum - A[i], A[], i + 1, Result + A[i])

Any combination of additions of a specified number set to reach a specific target value

1 Answers1