I've been working on a function that takes an array and an integer as parameters, returning an array of subarrays. The number of subarrays exactly matches the integer passed to the function, with each subarray containing continuous elements in the original order of the input array. None of the subarrays can be empty, they must contain at least one element. For example:
const array = [2,3,5,4]
const numOfSubarray = 3
const subarrays = getSubarrays(arraym numOfSubarray)
In this case, the resulting subarrays would look like this:
[
[[2, 3], [5], [4]],
[[2], [3, 5], [4]],
[[2], [3], [5, 4]],
]
This is the attempt I have made so far:
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 subarrays 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
}
Although it seems to be functioning correctly, I am curious about the time/space complexity of this algorithm. It appears to be slower than O(2^n). Are there ways to enhance its performance? Any alternative solutions that could improve the efficiency of this algorithm?