You can't get an answer down to anything like 2n, I'm afraid. This grows much faster than that, because the answer has to do with the binomial coefficients, whose definitions have fundamental factorial parts, and whose approximations involve terms like nn.

Your solution seems likely to be worse than necessary, noted because of the exponential number of calls required to solve the simplest case, when numOfSubarrays is 1, and you should just be able to return [array]. But as to full analysis, I'm not certain.

As the first comment shows, the above analysis is dead wrong.

However, if your're interested in another approach, here's how I might do it, based on the same insight others have mentioned, that the way to do this is to find all sets of numOfSubarrays indices of the positions between your values, and then convert them to your final format:

const choose = (n, k) => 
  k == 0
    ? [[]]
  : n == 0
    ? []
    : [... choose (n - 1, k), ... choose (n - 1, k - 1). map (xs => [...xs, n])]

const breakAt = (xs) => (ns) =>
  [...ns, xs .length] .map ((n, i) => xs .slice (i == 0 ? 0 : ns [i - 1], n))

const subarrays = (xs, n) =>
  choose (xs .length - 1, n - 1) .map (breakAt (xs))


console .log (subarrays ([2, 3, 5, 4], 3) // combine for easier demo
  .map (xs => xs .map (ys => ys .join ('')) .join('-')) //=> ["23-5-4", "2-35-4", "2-3-54"]
)

console .log (subarrays ([2, 3, 5, 4], 3)) // pure result

.as-console-wrapper {max-height: 100% !important; top: 0}

Here, choose (n, k) finds all the possible ways to choose k elements from the numbers 1, 2, 3, ..., n. So, for instance, choose (4, 2) would yield [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]].

breakAt breaks an array into sub-arrays at a set of indices. So

breakAt ([8, 6, 7, 5, 3, 0, 9]) ([3, 5])
//                3     5  ///=> [[8, 6, 7], [5, 3], [0, 9]]

And subarrays simply combines these, subtracting one from the array length, subtracting one from numOfSubarrays, calling choose with those two values, and then for each result, calling breakAt with the original array and this set of indices.

Even here I haven't tried to analyze the complexity, but since the output is factorial, the process will take a factorial amount of time.

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.

tl;dr

The number of solutions is bound to (as @gimix mentioned) binomial coefficient, so if I understand correctly it's pessimistically exponential https://en.wikipedia.org/wiki/Binomial_coefficient#Bounds_and_asymptotic_formulas.

If I'm not mistaken that makes your algorithm this exponential * n (for each element of each solution) * n (because on nearly every step you copy array which length might be dependent on n).

• fix second if - only call recurse if subArrays.length < numOfSubarrays
• you are copying arrays a lot - slice, concat, spread operator - all of those create new arrays. If for every solution (which length might be depending on n) on every step you copy this solution (which I think is happening here) you multiply the complexity by n.
• the space complexity is also exponential * n - you store the exponential number of solutions, possibly of length dependent on n. Using a generator and returning one solution at the time could greatly improve that. As @gimix mentioned the combinations might be the simplest way to do it. Combinations generator in python: https://docs.python.org/3/library/itertools.html#itertools.combinations

Dwelling on complexity:

I think you are right about the slower than exponential complexity, but - bare with me - how much do you know about Fibonacci's sequence? ;)

Let's consider input:

array = [1, 2, ..., n]
numOfSubarrays = 1

We can consider the recursive calls a binary tree with if 1. guarding the left child (first recurse call) and if 2. guarding the right child (second recurse call).

For each recurse call if 1. will be fulfilled - there are more items than sub arrays needed.

Second if will be true only if current sub array has some elements. It's a tricky condition - it fails if, and only if, it succeeded one frame higher - an empty array has been added at the very beginning (except for the root call - it has no parent). Speaking in terms of a tree, it means we are in the right child - the parent must have just added an empty sub array as a current. On the other hand, for the left child parent has just pushed (yet another?) element to the current sub array and we are sure the if 2. will succeed.

Okay, but what does it say about the complexity?

Well, we can count the number of nodes in the tree, multiply by the number of operations they perform - most of them a constant number - and we get the complexity. So how many are there?

I'll keep track of left and right nodes separately on every level. It's gonna be useful soon. For convenience I'll ignore root call (I could treat it as a right node - it has empty sub array - but it messes up the final effect) and start from level 1 - the left child of the root call.

r₁ = 0
l₁ = 1

As a left node (sub array isn't empty) it has two children:

r₂ = 1
l₂ = 1

Now, the left node always has two children (1. is always fulfilled; 2. is true because parent pushed element to current sub array) and the right node has only the left child:

r₃ = r₂ + l₂ = 1 + 1 = 2
l₃ = r₂ = 1

we could continue. The results are:

well... it's oddly familiar, isn't it?

Okay, so apparently, the complexity is O(Σ(F_i + F_i-1) where 1 <= i <= n).

Alright, but what does it really mean? There is a very cool prove that S(n) - sum of the Fibonacci numbers from 0 to n is equal F(n+2) - 1. It simplifies the complexity to:

O(S(n) + S(n-1)) = O(F(n+2) - 1 + F(n+1) - 1) = O(F(n+3) - 2) = O(F(n+3))

We can forget about the +3 since F(n+3) < 2 * F(n+2) < 4 * F(n+1) < 8 * F(n).

The final question, is Fibonacci sequence exponential? Yes and no apparently. The is no number that would fulfil the xⁿ = F(n) - the value oscillates between 2 and √2, because for F(n+1) < 2 * F(n) < F(n+2).

It's proven though, that lim(n->∞) F(n+1) / F(n) = φ - the golden ratio. It means the O(F(n)) = O(φⁿ). (Actually, you copy arrays a lot, so it's more like O(φⁿ*n))

How to fix it? You could check if there isn't too many arrays before recursing in if 2.

Other than that, just as @Markus mentioned, depending on the input, the number of solutions might be exponential, so the algorithm to get them also has to be exponential. But that's not true for every input, so let's keep those cases to minimum :D

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