Trying to make a recursive function that returns all combinations of an input array. I keep getting a Type Error 'cannot read properties of undefied'

Question

I am stumped as to why I am getting the error because I am passing in an array that is defined and should have length. Yet, I keep getting the "Type Error on line XXX: Cannot read properties of undefined (reading 'length')"

Here is the code I am working on...

function getAllCombos(arr) {
    // declare an array to hold results
  let results = [];
  // declare an innerfunction which takes a prefix and the original array passed in
  function recurse(prefix, arr) { 
    // loop through the original array, our base case will be when the loop ends
    for (let i = 0; i < arr.length; i++) { 
    // push the results of spreading the prefix into an array along with the current element both in an array
    results.push([...prefix, arr[i]]);
    // recursive case: now we build the prefix, we recurse and pass into our prefix parameter an array consisting of the prefix spread in, the current element being iterated on, and the original array sliced after our current element
    recurse([...prefix, arr[i], arr.slice(i+1)])
    }
  }
  // call the inner function with an empry prefix argument and the original array
  recurse([], arr);
  // return the results array
  return results;
}

and here are some test cases...

console.log(getAllCombos(['a', 'b'])); // -> [['a','b'], ['a'], ['b'], []]
console.log(getAllCombos(['a', 'b', 'c']));
// -> [
//   ['a', 'b', 'c'],
//   ['a', 'b'],
//   ['a', 'c'],
//   ['a'],
//   ['b', 'c'],
//   ['b'],
//   ['c'],
//   [],
// ]

Can someone please explain to me why I keep getting this error message even though I am passing in an array that has length?

Thank you for any pointers!

Answer 1

where you went wrong

I think you are calling recurse wrong -

recurse([...prefix, arr[i], arr.slice(i+1)]) // <- notice `]`

Move the ] to after arr[i] -

recurse([...prefix, arr[i]], arr.slice(i+1))

a fresh start

That said, I think everything can be improved with use of a simpler function -

function* combinations(t) {
  if (t.length == 0) return yield []
  for (const combo of combinations(t.slice(1))) {
    yield [ t[0], ...combo ]
    yield combo
  }
}

// array
for (const combo of combinations(["a", "b"]))
  console.log(`(${combo.join(",")})`)
  
// or even strings
for (const combo of combinations("abc"))
  console.log(`(${combo.join(",")})`)

(a,b)
(b)
(a)
()

(a,b,c)
(b,c)
(a,c)
(c)
(a,b)
(b)
(a)
()

some optimization

Above .slice is effective but does create some unnecessary intermediate values. We could use an index, i, like you did in your original program -

function combinations(t) {
  function* generate(i) {
    if (i >= t.length) return yield []
    for (const combo of generate(i + 1)) {
      yield [ t[i], ...combo ]
      yield combo
    }
  }
  return generate(0)
}

for (const combo of combinations(["🔴","🟢","🔵","🟡"]))
  console.log(combo.join(""))
  

🔴🟢🔵🟡
🟢🔵🟡
🔴🔵🟡
🔵🟡
🔴🟢🟡
🟢🟡
🔴🟡
🟡
🔴🟢🔵
🟢🔵
🔴🔵
🔵
🔴🟢
🟢
🔴

To collect all values from a generator into an array, use Array.from -

const allCombos = Array.from(combinations(...))

• To computed fixed-size combinations, n choose k, see this Q&A
• To compute permutations using a similar technique, see this related Q&A

without generators

The chief advantage of using generators for combinatorics problems is each result is offered lazily and computation can be stopped/resumed at any time. Sometimes however you may want all of the results. In such a case, we can skip using a generator and eagerly compute an array containing each possible combination -

const combinations = t =>
  t.length == 0
    ? [[]]
    : combinations(t.slice(1)).flatMap(c => [[t[0],...c], c])
  
const result =
  combinations(["a", "b", "c"])
  
console.log(JSON.stringify(result))

[["a","b","c"],["b","c"],["a","c"],["c"],["a","b"],["b"],["a"],[]]