Easy C++ Backtracking and Memoization || DP || Simple Code Easy to Understand
\n# Code\n\n//Backtracking\nclass Solution {\npublic:\n    int solve(int index,vector<string> &ans,vector<string> &arr)\n    {\n        if(index>=arr.size()) re
\n# Code\n```\n//Backtracking\nclass Solution {\npublic:\n    int solve(int index,vector<string> &ans,vector<string> &arr)\n    {\n        if(index>=arr.size()) return 0;\n\n        ans.push_back(arr[index]);\n        unordered_map<char,int> m;\n        for(int i=0;i<ans.size();i++)\n        {\n            for(int j=0;j<ans[i].size();j++) m[ans[i][j]]++;\n        }\n\n        bool flag=1;\n        for(auto &val:m)\n        {\n            if(val.second>1)\n            {\n                flag=0;\n                break;\n            }\n        }\n        \n        int opt1=0,opt2=0;\n        if(flag) opt1=arr[index].size()+solve(index+1,ans,arr);\n        ans.pop_back();\n        opt2=solve(index+1,ans,arr);\n\n        return max(opt1,opt2);\n\n    }\n    int maxLength(vector<string>& arr) {\n        vector<string> ans;\n        \n        return solve(0,ans,arr);\n    }\n};\n```\n\n```\n//Memoisation\nclass Solution {\npublic:\n    int solve(int index,vector<string> &ans,vector<string> &arr,unordered_map<string,int> &dp)\n    {\n        if(index>=arr.size()) return 0;\n        \n        string curr="";\n        for(auto &val:ans) curr+=val;\n        \n        if(dp.find(curr)!=dp.end()) return dp[curr];\n\n        ans.push_back(arr[index]);\n        unordered_map<char,int> m;\n        for(int i=0;i<ans.size();i++)\n        {\n            for(int j=0;j<ans[i].size();j++) m[ans[i][j]]++;\n        }\n\n        bool flag=1;\n        for(auto &val:m)\n        {\n            if(val.second>1)\n            {\n                flag=0;\n                break;\n            }\n        }\n        \n        int opt1=0,opt2=0;\n        if(flag) opt1=arr[index].size()+solve(index+1,ans,arr,dp);\n        ans.pop_back();\n        opt2=solve(index+1,ans,arr,dp);\n\n        return dp[curr]=max(opt1,opt2);\n\n    }\n    int maxLength(vector<string>& arr) {\n        unordered_map<string,int> dp;\n        vector<string> ans;\n        \n        return solve(0,ans,arr,dp);\n    }\n};\n```\n
['Dynamic Programming', 'Backtracking', 'Recursion', 'C++']