How to memoize or make recursive function with no apparent pattern?

Question

Consider the following code, it was done for the Codeforces Round #731 (Div. 3), problem B https://codeforces.com/contest/1547/problem/B

In short, you are given a string and you are supposed to check if it's possible to create that string by sequentially adding letters in alphabetical order in either the front to the back of a string that starts empty.

Ex. the string "bac", you would first make the empty string be "a", then it can be either "ba" or "ab", then we try again and we get that based on the last result it now can be "bac", "cba", "abc", "cab". We get that is possible so we return true. We can only do this procedure up to 26 times.

My code would make a tree, grabbing a base string as the head, and two children nodes, one with the letter added to the front and one with the letter added to the back, if neither worked out, then I would repeat it again with the children nodes.

I rewrote my solution and sent a completely different one, but I still wanted to know if there was a way to optimize so it could actually be executed. The code works if n is around 14 or 15, it stutters a little bit but can finish; but once it goes to 20 it will not even finish.

#include <iostream>
#include <string>

using namespace std;


bool solve(string fs,string s = "", int n = 0){
    if(s == fs){
        return true;
    }
    if(n > 26 || s.size() > fs.size()){
        return false;
    }
    if(solve(fs,s+(char)(96+n+1),n+1) ||solve(fs,(char)(96+n+1)+s,n+1)){
        return true;
    }
    return false;
}

int main(){
    int t;cin>>t;
    for(int i = 0; i < t; i++){
        string p;
        cin>>p;
        if(solve(p)){
            cout<<"YES"<<endl;
        }
        else{
            cout<<"NO"<<endl;
        }
    }

}```

Answer 1

1. You are doing brute force approach which is time complexity of n * 2^n. And it looks pretty reasonable to fail(TLE) when n is around 20 (taking into account that t is up to 10000)
2. I cannot come up with a way for efficient memoization, however this problem can easily be solved with greedy approach. You don't have to check all the combinations. Check out the official editorial