My Approach and Code Iterate a pointer from 0 to i, if the number formed in substring s[0]...s[i] is prime, check whether the remaining string can be decomposed into prime numbers or not. This is the portion we can do using recursion. Further improve the time complexity using dp, as there will be many independent and repetitive subproblems. I haven't memoized the below code. primes is a vector containing all the prime numbers from 2 to 1000. It passed all the given cases.

int solve(int i, string s, int sum){
    if(i == s.size()){
        return sum == 0;
    }
    int ans = 0;
    int curr = 0;
    if(s[i] == '0'){
        return 0;
    }
    for(int j=i; j<s.size(); j++){
        curr = curr*10 + s[j]-'0';
        if(binary_search(primes.begin(), primes.end(), curr)){
            ans += solve(j+1, s, 0);
        }
    }
    
    return ans;
}
int split_primes(std::string s) {
    return solve(0, s, 0);
}