@stellari can you explain where N - 2 comes from in the recurrence relation for the time complexity?
T(N) = (N - 2) * T(N - 2)
Shouldn't it be,
T(N) = (N - 1) * T(N - 2)
where (N - 1) is the number of pairs that can be formed from a string of length N consisting of all '+'?
Also, that does not account for the cost of copying the array each time.