Number of longest common subsequences

I need to find the number of distinct longest common subsequences between two strings A and B. I am currently using a normal dynamic programming approach and then generate all the different substrings using a backtracking array and then doing the first depth search from the starting index.

However, since there are so many possible answers, my code is too slow. Is there a way to count the number of such individual longest common subsequences without generating them at all?

My code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Stack;

class Node
{
String res = "";
int i;
int j;

public Node( int _i, int _j, String s )
{
    i = _i;
    j = _j;
    res = s;
}
}

public class LCSRevisited
{
static String a;
static String b;
static int m,n;
static int[][] memo;
static int[][] bt; // 1 means [i+1][j], 2 means [i][j+1], 3 means [i+1][j+1]
// 4  - means both

static HashSet <String> filter;

static void printAllStrings( )
{
    Iterator i = filter.iterator();

    while( i.hasNext())
    {
        System.out.println( i.next() );
    }
} 

 static void printSol()
 {
   System.out.print( memo[ 0 ][ 0 ]);

   // check how many UNIQUE such strings exist

   filter = new HashSet();
   Stack<Node> s = new Stack();
   Node start = new Node( 0, 0, "" );
   s.push( start );
   Node curr;
   String res;

   // use backtrack array to do a DFS

   while( !s.isEmpty() )
   {
        curr = s.pop();
        res = curr.res;

        if( ( curr.i>=m) || ( curr.j >=n ) )
        {
            filter.add( curr.res);
            continue;
       }

        // check backtrack value
        int i = curr.i;
        int j = curr.j;
        int back = bt[ i ][ j];

        if( back == 1 )
        {
            s.push( new Node( i+1, j, res ));
        }
        if( back == 2 )
        {
            s.push( new Node( i, j+1, res ));
        }
        if( back == 3 )
        {
            s.push( new Node( i+1, j+1, res+a.charAt(i) ));
        }
        if( back == 4 )
        {
            s.push( new Node( i, j+1, res ));
            s.push( new Node( i+1, j, res ));
        }
   }
   //printAllStrings();
   System.out.println(" " + filter.size() );
}

static void solve()
{
   // fill base cases
   m = a.length();
   n = b.length();
   memo = new int[ m+1 ][ n+1 ];
   Arrays.fill( memo[m], 0 );

   bt = new int[ m+1 ][ n+1 ];

   for( int i=0; i<m; i++ )
   {
       memo[ i ][ n ] = 0;    
   }

   // Now compute memo values
   for( int i=m-1; i>=0; i-- )
   {
       for( int j=n-1; j>=0; j-- )
       {
           if( a.charAt(i) == b.charAt(j))
           {
               memo[ i ][ j ] = 1 + memo[ i+1 ][ j+1 ];
               bt[ i ][ j ] = 3;
           }
           else
           {
               int r1 = memo[ i+1 ][ j ];
               int r2 = memo[ i ][ j+1 ];

               if( r1==r2 )
               {
                    memo[ i ][ j ] = r1;
                    bt[ i ][ j ] = 4;
               }
               else if( r1 > r2 )
               {
                   memo[ i ][ j ] = r1;
                   bt[ i ][ j ] = 1;
               }
               else
               {
                   memo[ i ][ j ] = r2;
                   bt[ i ][ j ] = 2;
               }
           }
       }
   }

   printSol();
 }

public static void main( String[] args ) throws IOException
{
 BufferedReader br = new BufferedReader( new InputStreamReader( System.in ));

int T= Integer.parseInt( br.readLine() );

while( T--> 0 )
{
    a = br.readLine();
    b = br.readLine();

    if( T>=1 )
    br.readLine();

    solve();
    // printArr( bt );
}
}
}