0

I made this function to get all possible combinations of a set that sum to a target value, its works, but it is not as organize/efficient as possible yet. After fry my brain trying to optimize this function i ran out of ideas and a litle bit blind, so i came here to get somes adivices and ideas for what more i can do.

const combinate = (set, target) => {
    const result = []
    set.forEach((element) => {
        let division = Math.floor(target / element)
        let remainder = target % element

        while (remainder !== target) {
            let combinations = []

            for (let index = 0; index < division; index++) {
                combinations.push(element)
            }

            if (remainder === 0) {
                result.push(combinations.sort())
                break
            } else if (set.includes(remainder)) {
                combinations.push(remainder)
                result.push(combinations.sort())
                break
            } else {
                division--
                remainder += element
            }
        }
    })

    return result
}

Here I have some examples of expected outcomes for how this function it should work.

combinate([2, 3, 5], 8) -> [[2,2,2,2],[2,3,3],[3,5]]

Scott Sauyet
  • 49,207
  • 4
  • 49
  • 103
codeperson
  • 1
  • 1
    This problem is called *Subset sum with repetition*. It's not too easy to solve it, but take a look at this answer: https://stackoverflow.com/a/53838665/4403732 - it seems to work fine, except some subsets are repeated. You can use it and filter out repetitions. – Robo Robok Oct 13 '21 at 20:09
  • I don't know the name of this challenger, but now you told me it will easier to find about in internet, i will take a look in this answer too, thank you very much. – codeperson Oct 14 '21 at 14:48
  • in my case, it is only permite use two parameters in function, because of this, some more efficient solution options ended up not being viable. – codeperson Oct 14 '21 at 14:53
  • That's fine - this function uses 3rd and 4th parameter only for its own purpose (recurrence). – Robo Robok Oct 14 '21 at 15:27

1 Answers1

0

I think your algorithm is fine.

I personally would structure the code differently, as I'm a fan of expression-only coding. My version might look like this:

// Ex: countDown (6) //=> [6, 5, 4, 3, 2, 1, 0]
const countDown = (n) => 
  n < 0 ? [] : [n, ...countDown (n - 1)]

const subsetSum = ([n, ...ns], t) =>
  n == undefined
    ? t == 0 ? [[]] : []
  : countDown (Math.floor (t / n)) .flatMap (
      (k) => subsetSum (ns, t - k * n) .map (ss => [...Array (k) .fill (n), ...ss])
    )

console .log (subsetSum ([2, 3, 5], 8))
.as-console-wrapper {max-height: 100% !important; top: 0}

I count down rather than up just so the results come in the same order yours did. If I counted up, they would show up as [[3, 5], [2, 3, 3], [2, 2, 2, 2]].

But this is essentially the same algorithm as yours. If it's ill-performant, then I might look at a dynamic programming version where we calculate the results for each lower total, and then for our target total, we look up the values found by subtracting each of the number in our set, and for each of those results, we add one of that number. Here's one version:

const countUp = (n) => 
  (n < 1) ? [] : [... countUp (n - 1), n]

const oneMore = (i) => (s) =>
  s .split ('-') .map (Number) .map ((n, j) => j == i ? n + 1 : n) .join ('-')

const collect = (ns, t) => 
  countUp (t) .reduce (
    (rs, v) => [
      ...rs, 
      new Set (ns .flatMap ((n, i) => ([...rs [v - n] || []]) .map (oneMore (i))))
    ],
    [new Set([ns .map (n => 0) .join ('-')])]
  ) 

const subsetSum = (ns, t) =>
  [...collect (ns, t) [t]]
    .map (s => s.split ('-') .map(Number) .flatMap ((c, i) => Array (c) .fill (ns[i])))

console .log (subsetSum ([2, 3, 5], 8))
.as-console-wrapper {max-height: 100% !important; top: 0}

The main function here, collect accepts, say [2, 3, 5] and 8, and returns something like

[
  new Set (['0-0-0']),                   // 0
  new Set ([]),                          // 1
  new Set (['1-0-0']),                   // 2
  new Set (['0-1-0']),                   // 3
  new Set (['2-0-0']),                   // 4
  new Set (['1-1-0', '0-0-1']),          // 5
  new Set (['3-0-0', '0-2-0']),          // 6
  new Set (['2-1-0', '1-0-1']),          // 7
  new Set (['4-0-0', '1-2-0', '0-1-1']), // 8
]

where, say '1-1-0' represents one 2 and one 3 and zero 5s, which add up to 5, or '0-1-1' represents zero 2s and one 3 and one 5, which add up to 8. In retrospect, a better string format would probably have been the JSON-stringified version of something like {2: 1, 3: 1, 5: 0} But I'll leave that as an exercise.

The values are stored as Strings in Sets to eliminate duplicates as we go. For instance, when we hit 5, we can add a 2 to '0-1-0' or a 3 to '1-0-0', both of which end up as '1-1-0'. But we only want a single copy of that result.

We use two minor helper functions. countUp for instance, turns 7 into [1, 2, 3, 4, 5, 6, 7]. oneMore handles the string to Array of numbers back to string conversion such that

    oneMore (0) ('1-7-4') //=> '2-7-4'
    oneMore (1) ('1-7-4') //=> '1-8-4'
    oneMore (2) ('1-7-4') //=> '1-7-5'

The main function simply extracts the last value computed by collect and then for each of the Strings in the set, converts that back into a proper array.

I have not tested for performance, but there's a real chance that this will be faster than the original algorithm. If nothing else, it demonstrates a substantially different technique.

Scott Sauyet
  • 49,207
  • 4
  • 49
  • 103