Finding all possible combinations of array items in JS

Published on in JavaScript

Last updated on

Example: converting [1, 2, 3] into [[1],  [2],  [1, 2],  [3],  [1, 3],  [2, 3],  [1, 2, 3]].

Table of contents

Why?

I recall needing this a few times, maybe when solving Advent of Code puzzles.

Plus I really like my solution. I find it straightforward, maybe even obvious now. But it took me a while to come up with it – my first attempts were much more complex and didn't even work properly – and maybe that's why I'm keen on this simple solution.

Example input and output

const array = [1, 2, 3, 4]
getCombinations(array)
/* =>
  [
    [1],
    [2],
    [1, 2],
    [3],
    [1, 3],
    [2, 3],
    [1, 2, 3],
    [4],
    [1, 4],
    [2, 4],
    [1, 2, 4],
    [3, 4],
    [1, 3, 4],
    [2, 3, 4],
    [1, 2, 3, 4],
  ]
*/

Code

const getCombinations = (items) =>
  items.reduce((combos, item) => {
    const newCombos = combos.map((combo) => combo.concat(item))
    combos.push([item], ...newCombos)
    return combos
  }, [])

Probably not the most efficient solution, but straightforward and easy. And no for loops!

Order of combinations

The order of the final combinations change if you change the order of the push method's arguments:

const items = [1, 2, 3]

items.reduce((combos, item) => {
  const newCombos = combos.map((combo) => combo.concat(item))
  combos.push([item], ...newCombos)
  return combos
}, [])
//=> [[1],  [2],  [1, 2],  [3],  [1, 3],  [2, 3],  [1, 2, 3]]

// versus

items.reduce((combos, item) => {
  const newCombos = combos.map((combo) => combo.concat(item))
  combos.push(...newCombos, [item])
  return combos
}, [])
//=> [[1],  [1, 2],  [2],  [1, 3],  [1, 2, 3],  [2, 3],  [3]]

In some cases the order might matter.

Beware too large input arrays

The code doesn't work if the input array's length is 20+:

getCombinations(Array.from({ length: 19 })) // OK
getCombinations(Array.from({ length: 20 })) // RangeError

More details in Part 2: Finding array item combinations for large arrays is complex.

Mutation

Notice how I'm mutating the accumulator array (combos) in the reducer function?

Mutations can be bad, but in this case they are okay, because local mutations are all right.