Get all partitions of an array into k non-empty sub-arrays

Question

I am writing a function that takes an array and an integer number and returns an array of all the partitions into subarrays (so an array of arrays of subarrays). The number of subarrays is exact the integer number passed to the function. And the subarrays have to be continuous, meaning the original order of items in the array has to be preserved. Also no subarray can be empty. They have to have at least one item in it. For example:

const array = [2,3,5,4]
const numOfSubarray = 3

const subarrays = getSubarrays(array, numOfSubarray)
// [[[2, 3], [5], [4]], [[2], [3, 5], [4]], [[2], [3], [5, 4]]]

Here is my attempt:

function getSubarrays(array, numOfSubarray) {
  const results = []

  const recurse = (index, subArrays) => {
    if (index === array.length && subArrays.length === numOfSubarray) {
      results.push([...subArrays])
      return
    }
    if (index === array.length) return

    // 1. push current item to the current subarray
    // when the remaining items are more than the remaining sub arrays needed

    if (array.length - index - 1 >= numOfSubarray - subArrays.length) {
      recurse(
        index + 1,
        subArrays.slice(0, -1).concat([subArrays.at(-1).concat(array[index])])
      )
    }
    // 2. start a new subarray when the current subarray is not empty

    if (subArrays.at(-1).length !== 0)
      recurse(index + 1, subArrays.concat([[array[index]]]))
  }

  recurse(0, [[]])
  return results
}

Right now it seems to be working. But I wanted to know what is the time/space complexity of this algorithm. I think it is definitely slower than O(2^n). Is there any way to improve it? Or any other solutions we can use to improve the algorithm here?

Answer 1

Time and space complexity

To calculate the time and space complexity, it's useful to consider the output: what must it contain. For every way to split into sub-arrays, the output will contain one array, containing \$n\$ items across another level of sub-arrays.

How many ways can we split \$n\$ items to \$k\$ non-empty sub-arrays? There are \$n-1\$ "cutpoints" along which we can split. To split to \$k\$ sub-arrays, we have to select \$k-1\$ cutpoints. How many ways can we select \$k-1\$ cutpoints out of \$n-1\$ candidates? That follows nCk, aka n-choose-k, aka the binomial coefficient:

$$ \binom{n}{k} = \frac{n!}{k!(n-k)!} $$

That's how many sub-arrays will be in the output, and each of those will contain \$n\$ items across their sub-arrays.

Therefore the time and space complexity is \$O(\binom{n}{k})\$. It is faster than \$O(2^n)\$.

In the implementation I don't see excessive computations or wasted storage to make the order of time or space complexity worse.

One notable wasted computation in the implementation is the unnecessary array copy here:

results.push([...subArrays])

The copy is unnecessary, because subArrays is never modified, only copies of it are passed to recursive calls. So you can simply do:

results.push(subArrays)

Validate inputs

If more sub-arrays are requested than the number of items in the input, that looks like a mistake by the caller, so it makes sense to throw an error to signal that something's wrong, rather than silently carry on. The same goes for less than 1 sub-arrays.

Improving readability

I think the implementation can be written a bit simpler, following slightly different steps. In particular, it would be good to make the main logic of the recursion more clear. That is, it's essentially about taking two possible paths:

• If there are more than enough items in the input to make the required sub-arrays, then add the current item to the last sub-array

• If there are more sub-arrays to make, then start a new sub-array with the current item

• If there are no more items in the input, then add the current positioning sub-arrays to the answer and stop the recursion (this should be the first step in the recursive function)

For example:

function getSubarrays(array, targetSubArrayCount) {
  if (array.length < targetSubArrayCount) throw Error("Not enough items to make sub-arrays")
  if (targetSubArrayCount < 1) throw Error("The number of sub-arrays must be >= 1")

  const results = []
  if (array.length == 0) return results

  function recurse(index, subArrays, remaining) {
    if (index == array.length) {
      results.push(subArrays)
      return
    }

    if (array.length - index > remaining) {
      // we have enough elements to add to the last sub-array
      recurse(
        index + 1,
        subArrays.slice(0, -1).concat([subArrays.at(-1).concat(array[index])]),
        remaining
      )
    }

    if (remaining > 0) {
      // we have to add more sub-arrays
      recurse(
        index + 1,
        subArrays.concat([[array[index]]]),
        remaining - 1
      )
    }
  }

  recurse(1, [[array[0]]], targetSubArrayCount - 1)
  return results
}