Forming all multiples of 3 using the given digits
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.