Hi,

I was trying to code a problem on printing all possible LIS of a string in sorted order. The link to the problem is http://www.spoj.com/problems/UPSUB/. My idea is simply to calculate a 2D LCS matrix by LCS(string s, sort(string s)) and then backtrack over the LCS matrix with optimization to get all the LIS. I am facing problems in optimizing my backtracking code because its visiting way too many states that required.

#include <bits/stdc++.h>
using namespace std;
/*u,l,d correspond to the possible directions from which the maximum value of the LCS array came from*/
struct node{
    int val,u,l,d;
};
int n,maxlen;
set<string> ans;
string s,s1;
//int vis[110][110];
vector<vector<node > > dp;
/*calculates LIS=LCS(s,sort(s))*/
void lis(void){
    s1=s;
    sort(s1.begin(),s1.end());
    //cout<<s1<<endl;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=n;j++){
            if(s1[i-1]==s[j-1]){
                /*if(i==1 and j==2)
                    cout<<"Came wrong way "<<endl;*/
                int x=max(max(dp[i-1][j].val,dp[i][j-1].val),dp[i-1][j-1].val+1);
                dp[i][j].val=x;
                if(dp[i-1][j].val==x){
                    dp[i][j].u=1;
                }
                if(dp[i][j-1].val==x){
                    dp[i][j].l=1;
                }
                if((dp[i-1][j-1].val+1)==x){
                    dp[i][j].d=1;
                }
            }
            else{
                int x=max(dp[i-1][j].val,dp[i][j-1].val);
                dp[i][j].val=x;
                if(dp[i-1][j].val==x){
                    dp[i][j].u=1;
                }
                if(dp[i][j-1].val==x){
                    dp[i][j].l=1;
                }
            }
        }
    }
    maxlen=dp[n][n].val;
    //cout<<maxlen<<endl;
}
string st;
void dfs(int x,int y){
    cout<<"now at "<<x<<"\t"<<y<<endl;
    if(x==0 or y==0){
        if(st.size()==maxlen){
            set<string>::iterator it=ans.begin();
            ans.insert(it,st);
            //cout<<"print at "<<x<<"\t"<<y<<endl;
        }
        return;
    }
    if(dp[x][y].d==1 ){
        st=s[y-1]+st;
        dfs(x-1,y-1);
        st.erase(st.begin(),st.begin()+1);
    }
    if(dp[x][y].u==1){
        dfs(x-1,y);
    }
    if(dp[x][y].l==1){
        dfs(x,y-1);
    }
}
void print_lis(void){
    for(int i=0;i<=n;i++){
        cout<<endl;
        for(int j=0;j<=n;j++){
            cout<<dp[i][j].val<<"\t";
        }
    }
    cout<<endl;
}
int main(void){
    int tc;
    cin>>tc;
    while(tc--){
        cin>>s;
        n=s.size();
        dp.resize(n+1);
        for(int i=0;i<=n;i++){
            dp[i].resize(n+1);
        }
        lis();
        //print_lis();
        dfs(n,n);
        //sort(ans.begin(),ans.end());
        for(set<string>::iterator it=ans.begin();it!=ans.end();it++)
            cout<<*it<<endl;
    }
    return 0;
}

Please suggest me some ways by which I can optimize the dfs(i,j) part.