Recursion [C++] Explanation
I think the commented code is enough for the explanation.\nfor n <= 12:\n we have 3 option for every position\nso we can simply use recursion with a Time-Comple
I think the commented code is enough for the explanation.\nfor n <= 12:\n* we have 3 option for every position\nso we can simply use recursion with a Time-Complexity of **O(n * 3^n)**\n\n* we have maximum of (length(a)+length(b)) length string in any path in the recursion\nso Space Complexity: **O(n)**\n\n**Note**: Don\'t mess up with pass by reference(&)\n\n```\nclass Solution {\npublic:\n    bool isPalindrome(string &a) {\n        int i = 0, j = a.length()-1;\n        while(i <= j) {\n            if(a[i++] != a[j--]) return false;\n        }\n        return true;\n    }\n    \n    void solve(string &s, int i, int n, string &a, string &b, int &res) {\n        if(isPalindrome(a) && isPalindrome(b)) { // both subsequences are palindrome\n            res = max(res, (int)a.length()*(int)b.length()); // take maximum of product of their length\n        }\n        if(i >= n) return ; // base case\n        \n        // case I: if we don\'t choose to add the current char to any of the subsequences\n        solve(s, i+1, n, a, b, res);\n        \n        // case II: if we choose to add the current char to a\n        a += s[i];\n        solve(s, i+1, n, a, b, res);\n        a.pop_back(); // backtrack\n        \n        // case III: if we choose to add the current char to b\n        b += s[i];\n        solve(s, i+1, n, a, b, res); \n        b.pop_back(); // backtrack\n    }\n    \n    int maxProduct(string s) {\n        int n = s.length();\n        string a = "", b = "";\n        int res = 1;\n        solve(s, 0, n, a, b, res);\n        return res;\n    }\n};\n```
['Backtracking', 'Recursion']