I am writing a function that takes an array and an integer number and returns an array 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(arraym numOfSubarray)

In this case subarrays is this:

[
  [[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, [[]], 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?

CodePudding user response：

If you want to completely split a list of n elements into k disjunct, continuous sub-lists this is like placing k-1 split points into the n-1 gaps between the elements:

2 | 3 | 5   4
2 | 3   5 | 4
2   3 | 5 | 4

In combinatorics this is taking k-1 from n-1. So I think the result size of the ouput will be n-1 take k-1 = (n-1)! / ((k-1)! * (n-k)!). Thus the complexity is something polynomial like O(n^(k-1)) for constant k. If you don't fix k but raise it with n like k = n/2 the complexity will get exponential.

I don't think that you can improve this, because the output's size is increasing by this complexity.

CodePudding user response：

The problem can be solved by a different approach:

• compute all the combinations of numOfSubarray numbers ranging from 1 to the length of array
• each combination is a valid slicing of array. For instance, you want to slice the array in your example at positions (1, 2), (1, 3), (2, 3), yielding subarrays [[2],[3],[5,4]], [[2],[3,5],[4]], and [[2,3],[5],[4]]

Time complexity is, I believe, O(r(nCr)) where n is (length of array - 1) and r is (number of subarrays - 1).

To visualize how and why it works have a look at the stars and bars technique