Backtracking+memoization is working . Why??
Doubt\n   Since to decide a unique state , we need:\n\n            1.index at which we are currently in string s\n            2.previous element chosen\n       
# Doubt\n   Since to decide a unique state , we need:\n\n            1.index at which we are currently in string s\n            2.previous element chosen\n            3.set of numbers that are used or left.Here vis vector.\n\n   But i have done memoization over first two, but the soln is working.Can\'t understand why??\n# Code\n```\n#define ll long long\nclass Solution {\npublic:\n    ll dp[202][202];\n    ll mod=1e9+7;\nint fun(int ind,int prev,int n,string&s, vector<bool>&vis)\n{\n    if(ind==s.size())\n    {\n        return 1;\n    }\n\n     if(dp[ind][prev]!=-1) return dp[ind][prev];\n    int ans=0;\n    if(s[ind]==\'D\')\n    {\n       for(int i=prev-1;i>=0;i--)\n       {\n         if(vis[i]==0)\n         {\n            vis[i]=1;\n            ans+=fun(ind+1,i,n,s,vis);\n            ans%=mod;\n            vis[i]=0;\n         }\n       }\n    }\n    else if(s[ind]==\'I\')\n    {\n        for(int i=prev+1;i<=n;i++)\n       {\n         if(vis[i]==0)\n         {\n            vis[i]=1;\n            ans+=fun(ind+1,i,n,s,vis);\n            ans%=mod;\n            vis[i]=0;\n         }\n       }\n    }\n   return dp[ind][prev]=ans;\n}\n\nint numPermsDISequence(string s) \n{\n    memset(dp,-1,sizeof(dp));\n    ll n=s.size();\n    vector<bool>vis(n+1,0);\n    int ans=0;\n    for(int i=0;i<=n;i++)\n    {\n        vis[i]=1;\n        ans+=fun(0,i,n,s,vis);\n        ans%=mod;\n        vis[i]=0;\n    }\n    //cout<<"ans="<<ans<<endl;\n    return ans;\n}\n};\n```
['Backtracking', 'Memoization', 'C++']