Why Backtracking + Memoization is working ??
To all Coders of the Leetcode Community this post needs to be addressed \nwhy this solution is working ??\n```\nclass Solution {\npublic:\n    \n    int mod = 1
To all Coders of the Leetcode Community this post needs to be addressed \nwhy this solution is working ??\n```\nclass Solution {\npublic:\n    \n    int mod = 1e9 + 7;\n    \n    int n;\n    \n    vector<int> vis;\n    \n    int dp[202][202];\n    \n    long long func(int i,int j,string &s){\n        if(i == n) return 1;\n        if(dp[i][j] != -1) return dp[i][j];\n        long long ans=0;\n        if(s[i] == \'D\'){\n            \n            for(int k=j-1;k>=0;k--){\n                if(vis[k] == false){\n                    vis[k] = true;\n                    long long tmp = func(i+1,k,s);\n                    ans += tmp;\n                    ans%=mod;\n                    vis[k] = false;\n                }\n            }\n        }else{\n            for(int k=j+1;k<=n;k++){\n                if(vis[k] == false){\n                    vis[k] = true;\n                    long long tmp = func(i+1,k,s);\n                    ans += tmp;\n                    ans%=mod;\n                    vis[k] = false;\n                }\n            }\n        }\n        \n        return dp[i][j] = ans;\n        \n    }\n    \n    int numPermsDISequence(string s) {\n        \n        n = s.size();\n        memset(dp,-1,sizeof(dp));\n        \n        vis = vector<int> (n+1,false);\n        \n        long long ans = 0;\n        for(int i=0;i<=n;i++){\n            vis[i] = true;\n            long long tmp = func(0,i,s);\n            ans += tmp;\n            ans%=mod;\n            vis[i] = false;\n        }\n        \n        return ans;\n        \n    }\n};
[]