Does this LCS algo generate all the CS or only all the LCSs?

Question

The Wikipedia article on LCS has an algorithm that backtracks all the LCS strings. This link redirects to the desired bulletin in the article. The C table in the backtrackAll function is pre-calculated, if you go up a tad bit. C[i][j] stores the LCSLength for given str1[1...i], str2[1...j].

(screenshot, for a quicker reference)

1. My understanding is that it generates all the common sequences since either or both if conditions at the end are satisfied, which runs the program for the sub-cases. Once the last letters are matched, every string upto that point (with the current X[i] as the last letter) is printed.

I somewhere fail to digest the algorithm properly and completely. An explanation might help me very much.

2. In the penultimate if, does changing writing the piece of code as R := R $\cup$ backtrackAll(C, X, Y, i, j-1) (instead of R := backtrackAll(C, X, Y, i, j-1)) change anything? I feel that it doesn't, given it's a top down approach and it only unions with the empty set R = {} above. Note that R is already defined above and the if is reached only after going through that empty set definition step, which rules out the possibility of having an error output.

Answer 1

Wikipedia is being sloppy. The procedure returns all LCSs of $X[1..i]$ and $Y[1..j]$, which corresponds to $C[i,j]$. It should mention that in order to obtain all LCSs, we need to set $i=m$ and $j=n$.

If $X[i] = Y[j]$, then every LCS of $X[1..i]$ and $Y[1..j]$ is obtained by taking an LCS of $X[1..i-1]$ and $Y[1..j-1]$, and adding to it $X[i] = Y[j]$.

If $X[i] \neq Y[j]$, then every LCS of $X[1..i]$ and $Y[1..j]$ must be either an LCS of $X[1..i-1]$ and $Y[1..j]$, or an LCS of $X[1..i]$ and $Y[1..j-1]$ (or both). If $C[i-1,j] > C[i,j-1]$, then only the former are LCSs of $X[1..i]$ and $Y[1..j]$. If $C[i-1,j] < C[i,j-1]$, then only the latter are LCSs of $X[1..i]$ and $Y[1..j]$. If $C[i-1,j] = C[i,j-1]$, then both types are LCSs of $X[1..i]$ and $Y[1..j]$.

This recursive procedure could count the same sequence more than once — this happens for example for the arrays $ab$ and $ac$, where $a$ will be reached twice.