explained why backtrack + memorization working
why it works without explicitly saving the state of the visited array?\n\n\nWhen we backtrack and return from a recursive call, we reset _ visited[curr] to fals
why it works without explicitly saving the state of the visited array?\n\n\nWhen we backtrack and return from a recursive call, we reset ```_ visited[curr] to false _``` which means that the state of visited is restored to what it was before the recursive call.\n\nThe memoization table dp is used to store and retrieve previously computed results for specific combinations of curr and index. This allows the algorithm to avoid redundant calculations and significantly improves its efficiency.\n\nIn summary, while the visited array is modified during the recursion, it is effectively reset to its original state when backtracking,``` _ thanks to the visited[curr] = false statement _ ``` \nThe state of visited is managed correctly within the recursive calls, and the memoization table dp ensures that previously computed results are reused to avoid unnecessary computations. This is why the algorithm works correctly without explicitly saving the state of the visited array.\n\n```\nclass Solution {\npublic:\n    string s="";\n    int n;\n    int dp[203][203];\n    int m=1e9+7;\n    int solve(int idx,int prev, vector<int>&vis)\n    {\n        if(idx==n) return 1;        \n        if(dp[idx+1][prev+1]!=-1) return dp[idx+1][prev+1];\n        long long ans=0;\n        if(idx==-1)\n        {\n            for(int i=0; i<=n; i++) \n            {\n                vis[i]=1;\n                ans+=solve(0,i,vis)%m;\n                ans%=m;\n                vis[i]=0;\n            }\n        }else\n        {\n            for(int i=0; i<=n; i++)\n            {\n                if(vis[i]==0 )\n                {\n                    if(s[idx]==\'D\' &&i<prev)\n                    {\n                        vis[i]=1;\n                        ans+=solve(idx+1,i, vis)%m;\n                        ans%=m;\n                        vis[i]=0;\n                    }else if(s[idx]==\'I\' && i>prev)\n                    {\n                        vis[i]=1;\n                        ans+=solve(idx+1,i, vis)%m;\n                        ans%=m;\n                        vis[i]=0;\n                    }\n                }\n            }\n        }\n        return dp[idx+1][prev+1]=(int)ans;\n    }\n    \n    int numPermsDISequence(string s1) \n    {\n        s=s1;\n        n=s.size();\n        vector<int> vis(n+1,0);\n        memset(dp,-1,sizeof(dp));\n        return solve(-1,-1,vis);\n    }\n};\n\n\n```
['Backtracking', 'Memoization', 'C']