@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.