How to print all possible solutions for Longest Common subsequence

Question

I want to print all the possible solutions to LCS problem.

The two strings abcbdab and bdcaba should print following 3 strings: bdab,bcba,bcab.

C is the global matrix table which takes values according to algorithm and m, n are the length of the sequences a, b.

But The output is something unexpected.

#include<stdio.h>
#include<conio.h>
int co=0,m=0,n=0,c[10][10];
char a[10],b[10];
void main()
{
    int i,j;
    clrscr();
    printf("Enter Two strings: ");
    scanf("%s",a);
    scanf("%s",b);
    m=strlen(a);
    n=strlen(b);
    for(i=0;i<=m;i++)
    {
        for(j=0;j<=n;j++)
        {   if(i==0 || j==0)
            {
                c[i][j]=0;
            }
            else if(a[i-1]==b[j-1])
            {
                c[i][j]=c[i-1][j-1]+1;
            }
            else if(c[i-1][j]>=c[i][j-1])
            {
                c[i][j]=c[i-1][j];
            }
            else
            {
                c[i][j]=c[i][j-1];
            }
        }
    }
    for(i=0;i<=m;i++)
    {
        for(j=0;j<=n;j++)
        {
            printf("%d\t",c[i][j]);
        }
        printf("\n");
    }
    print(m,n);
    getch();
}
print(int i,int j)
{
    if(i==0 || j==0)
        return 0;
    else if(a[i-1]==b[j-1])
    {
        print(i-1,j-1);
        if(co==c[m][n])
        {
            co=0;
            printf("\n");
        }
        printf("%c",a[i-1]);
        co++;
    }
    else if(c[i-1][j]==c[i][j-1])
    {
        print(i-1,j);
        print(i,j-1);
    }
    else if(c[i][j-1]>=c[i-1][j])
        print(i,j-1);
    else
        print(i-1,j);
    return;
}

Answer 1

Here you can find a recursive approach of how to do this: Reading out all LCSs

Here is my code for this approach in Java:

private Set<String> lcs(int[][] dp, String fst, String snd, int i, int j) {
    Set<String> lcss = new HashSet<>();

    if (i == 0 || j == 0) {
        lcss.add("");
    } else if (fst.charAt(i - 1) == snd.charAt(j - 1)) {
        for (String lcs : lcs(dp, fst, snd, i - 1, j - 1)) {
            lcss.add(lcs + fst.charAt(i - 1));
        }
    } else {
        if (dp[i - 1][j] >= dp[i][j - 1]) {
            lcss.addAll(lcs(dp, fst, snd, i - 1, j));
        }

        if (dp[i][j - 1] >= dp[i - 1][j]) {
            lcss.addAll(lcs(dp, fst, snd, i, j - 1));
        }
    }
    return lcss;
}