From Length to Sequences: Backtracking Through the LCS Table

Finding the LCS length was one thing. But what if the question asks for ALL possible longest subsequences? That's where backtracking enters the picture.

The New Challenge

Remember our example: s1 = "acabac", s2 = "aebab" gave us LCS length = 3.

But there are multiple valid sequences of length 3: "aba", "aab", etc. How do we find them all?

The Two-Step Approach

1. Build the DP table (we already know this part)
2. Backtrack through the table to collect all sequences

The key insight: the DP table doesn't just store lengths—it stores paths. When multiple paths lead to the same optimal value, we need to explore ALL of them.

Understanding the Backtrack Logic

Starting from dp[m][n] (bottom-right), we trace backwards:

When characters match (s1[i-1] == s2[j-1]):

• This character MUST be part of the LCS
• Move diagonally: (i-1, j-1)

When characters don't match:

• Check where the current value came from
• If dp[i-1][j] == dp[i][j] → we could have come from TOP
• If dp[i][j-1] == dp[i][j] → we could have come from LEFT
• If BOTH are true → explore BOTH paths (this is where multiple sequences come from!)

The Code

import java.util.*;

public class Solution {

    public List<String> allLCS(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();

        // Step 1: Build DP table (same as before)
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        // Step 2: Backtrack to find ALL sequences
        Set<String> result = new HashSet<>();  // Set removes duplicates
        backtrack(s1, s2, m, n, dp, "", result);

        return new ArrayList<>(result);
    }

    private void backtrack(String s1, String s2, int i, int j,
                          int[][] dp, String current, Set<String> result) {

        // Base case: reached the beginning of one string
        if (i == 0 || j == 0) {
            // We built the string backwards, so reverse it
            result.add(new StringBuilder(current).reverse().toString());
            return;
        }

        // Characters match - MUST include this character
        if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
            backtrack(s1, s2, i - 1, j - 1, dp,
                     current + s1.charAt(i - 1), result);
        }
        else {
            // Characters don't match - explore all optimal paths

            // Could we have come from TOP? (skipped s1[i-1])
            if (dp[i - 1][j] == dp[i][j]) {
                backtrack(s1, s2, i - 1, j, dp, current, result);
            }

            // Could we have come from LEFT? (skipped s2[j-1])
            if (dp[i][j - 1] == dp[i][j]) {
                backtrack(s1, s2, i, j - 1, dp, current, result);
            }
        }
    }
}

Walking Through the Backtrack

Let's trace what happens with "acabac" and "aebab":

DP Table (simplified view):
        ""  a  e  b  a  b
    ""   0  0  0  0  0  0
    a    0  1  1  1  1  1
    c    0  1  1  1  1  1
    a    0  1  1  1  2  2
    b    0  1  1  2  2  3
    a    0  1  1  2  3  3
    c    0  1  1  2  3  3

Starting at dp[6][5] = 3:

• s1[5]='c' ≠ s2[4]='b'
• dp[5][5]=3 (top) and dp[6][4]=3 (left) — BOTH equal current!
• So we explore BOTH branches

This branching is what gives us multiple sequences.

Why Backtracking Works Here

The DP table is like a map of all optimal decisions. When we backtrack:

• Single path: One sequence
• Multiple equal paths: Multiple sequences

We're not recalculating anything—just reading the map we already built.

Alternative: Recursive with Memoization

If you prefer building sequences forward instead of backward:

public List<String> allLCSRecursive(String s1, String s2) {
    Map<String, List<String>> memo = new HashMap<>();
    return func(s1, s2, 0, 0, memo);
}

private List<String> func(String s1, String s2, int i, int j,
                         Map<String, List<String>> memo) {

    // Base case
    if (i >= s1.length() || j >= s2.length()) {
        return new ArrayList<>(List.of(""));
    }

    String key = i + "," + j;
    if (memo.containsKey(key)) {
        return memo.get(key);
    }

    List<String> result = new ArrayList<>();

    if (s1.charAt(i) == s2.charAt(j)) {
        // Match - prepend this character to all sub-results
        for (String sub : func(s1, s2, i + 1, j + 1, memo)) {
            result.add(s1.charAt(i) + sub);
        }
    } else {
        // No match - get results from both directions
        List<String> skip1 = func(s1, s2, i + 1, j, memo);
        List<String> skip2 = func(s1, s2, i, j + 1, memo);

        int len1 = skip1.isEmpty() ? 0 : skip1.get(0).length();
        int len2 = skip2.isEmpty() ? 0 : skip2.get(0).length();

        // Only keep the longest ones
        if (len1 > len2) {
            result.addAll(skip1);
        } else if (len2 > len1) {
            result.addAll(skip2);
        } else {
            // Same length - keep both
            result.addAll(skip1);
            result.addAll(skip2);
        }
    }

    // Remove duplicates, keep only longest
    result = filterLongestUnique(result);
    memo.put(key, result);
    return result;
}

private List<String> filterLongestUnique(List<String> sequences) {
    if (sequences.isEmpty()) return sequences;

    int maxLen = sequences.stream()
                          .mapToInt(String::length)
                          .max()
                          .orElse(0);

    return sequences.stream()
                    .filter(s -> s.length() == maxLen)
                    .distinct()
                    .collect(Collectors.toList());
}

Key Takeaways

Finding Length	Finding All Sequences
Single value returned	List of strings returned
One path through recursion	Multiple paths (backtracking)
max() picks one winner	Equal values = explore both
O(m×n) space for DP	Additional space for sequences

The Pattern:

• DP gives you the optimal value
• Backtracking through DP gives you all ways to achieve that value

This pattern applies beyond LCS—anytime you need "all optimal solutions" instead of just "the optimal value," backtracking through your DP table is the answer.

---

This is a follow-up to Cracking Longest Common Subsequence. If you haven't read that one yet, start there for the fundamentals.