def _backtrack(matrix):
    """
    This generator backtracks through the matrix created by _build_lcs_matrix
    and yields each item of ONE of the possible largest common subsequences
    (LCS) from seq1 and seq2. Each item is a tuple of the form (i, j) It starts
    at the bottom right corner of the matrix and works backwards up to the top
    left.

    This is an interpretation of the algorithm presented on
    https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
    It has been generalised so that it works with lists rather than strings.
    It also uses while loop rather than recursion.
    """
    j = len(matrix) - 1
    i = len(matrix[0]) - 1
    while i > 0 and j > 0:
        current = matrix[j][i]
        up = matrix[j - 1][i]
        left = matrix[j][i - 1]
        if current == left:
            i -= 1
        elif current == up:
            j -= 1
        else:
            i -= 1
            j -= 1
            yield i, j
