Simple C++ solution | Recurrsion + Backtracking


#1
bool isPallindrome(string s) {
    int i = 0, j = s.length() - 1;
    while(i < j) {
        if (s[i] != s[j]) {
            return false;
        }
        i++;
        j--;
    }
    return true;
}

void fnc(string A, vector<string> &v, vector<vector<string>> &result) {
    // exit condition
    if (A.length() <= 0) {
        result.push_back(v);
        return;
    }
    
    int n = A.length();
    for(int i = 0; i < n; i++) {
        
        string copyString = A;
        string firstPart = A.substr(0, i + 1);
        string secondPart = A.substr(i + 1, n - i);
        
        if(isPallindrome(firstPart)) {
            v.push_back(firstPart);
            fnc(secondPart, v, result);
            // backtrack
            v.pop_back();
        }
    }
}

vector<vector<string> > Solution::partition(string A) {
    vector<vector<string>>result;
    vector<string>v;
    fnc(A, v, result);
    return result;
}