Forming all multiples of 3 using the given digits I'm working on this kata from Codewars. The task is:

Given a certain number, how many multiples of three could you obtain with its digits?
Supose that you have the number 362. The numbers that can be generated from it are:
362 → 3, 6, 2, 36, 63, 62, 26, 32, 23, 236, 263, 326, 362, 623, 632

I've written the following recursive function to calculate all possiblities:


const findMult_3 = (num) =&gt; {

  const powerset = (set) =&gt; {
    const combinations = []
    const combine = (prefix, chars) =&gt; {
      for (let i = 0; i &lt; chars.length; i++) {
        const newPrefix = parseInt(prefix + chars[i])
        if (!combinations.includes(newPrefix)) {
          combinations.push(newPrefix)
        } else {
          console.log('encountered duplicate')
        }
        combine(newPrefix, chars.filter((x, ind) =&gt; ind !== i))
      }
    }
    combine('', set)
    return combinations.sort((a, b) =&gt; a - b)
  }

  const allCombinations = powerset(num.toString().split(''))
  const factorsOfThree = allCombinations.filter(x =&gt; x % 3 === 0).filter(x =&gt; x !== 0)

  return [factorsOfThree.length, factorsOfThree.pop()]

}

findMult_3(43522283000229)



I noticed early on that I encountered a lot of duplicate cases, hence the console.log('encountered duplicate') flag.
Execution of this algorithm is taking an extremely long time for large numbers, eg 43522283000229.
How can I improve the performance of this code? Or should it be scrapped entirely?
How can I improve the performance of this code? Or should it be scrapped entirely?


I personally would consider taking a wildly different approach, but there are major performance improvements which can be made and which might be sufficient for your purposes.


        if (!combinations.includes(newPrefix)) {
          combinations.push(newPrefix)
        }



combinations is an array: combinations.includes is a linear search. I understand from the question that you're using Node, so the best way to improve this is probably hashset. However, if you want to stick to JavaScript primitives you can achieve a similar (albeit hacky) performance improvement by using an object as a hashmap:

        if (!combinations.hasOwnProperty(newPrefix)) {
          combinations[newPrefix] = 1;
        }





         else {
          console.log('encountered duplicate')
        }



If you also use a map for the remaining digits, you can ensure that you only try to extend with each digit once, and avoid the unnecessary work of handling duplicates.



I said that I would consider a wildly different approach. In combinatorics, if you only want to count objects then ideally you don't generate them all. You may have been taught in primary school that you can check whether a number is a multiple of 3 by adding its digits and seeing whether you get a multiple of 3. What's really going on there is that \$10 \equiv 1 \pmod{3}\$, so \$10^n \equiv 1 \pmod{3}\$ for any non-negative integer \$n\$. Thus you can cluster numbers by their values modulo 3. There are various directions in which this can be taken, and the need to avoid duplicates complicates things, so I suggest that you first try the earlier suggestions.