The space complexity can actually be less than O(n) with 2 dynamically allocated vectors
E.g at step H(21)
P
|
R = 1 3 7 12 18 26 35 45 56 69 83 98 114 131 150 170 191 213 236 260
S = 2 4 5 6 8 9 10 11 13 14 15 16 17 19 20 21 22 23 24 25We know that
R(21) = R(20) + S(20)
S(21) = S(20) + 1, if S(20) + 1 ∉ R(1,...,20)
S(21) = S(20) + 2, if S(20) + 1 ∈ R(1,...,20)The precedent algorithm allocated an array of size 21 and kept a pointer P to R(5)=26, the next value to skip when S(n - 1) + 1 reaches it.
But to compute the next P = S(6) = R(5) + S(5) = 35 we only need to store
R = 1 3 7 12 18 26
S = 2 4 5 6 8 9(we can't just store the last two values, because computing S(n + 1) would require backtracking and time complexity will explode)