Word Break

#include <bits/stdc++.h>
using namespace std;


// added a level parameter to see the prefix at each level and their recursive calls
void wordBreak(string word, vector<string> &pathString, unordered_set<string> &dictionary, int level){
    if(word.size() == 0){
        for(string s : pathString){
            cout << s << " ";
        }
        cout << '\n';
        return;
    }
    //create different prefix and see if it is a valid word in dictionary
    for(int i = 1; i <= word.size(); i++){
        string prefix = word.substr(0, i);
        if(dictionary.count(prefix)){
            pathString.push_back(prefix);
            string ros = word.substr(i);
            // cout << prefix << " " << level << '\n';
            wordBreak(ros, pathString, dictionary, level + 1);
            pathString.pop_back();
        }
    }
}

int main() {
    // your code goes here
    int n;
    cin >> n;
    string word;
    unordered_set<string> dictionary;
    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        dictionary.insert(s);
    }
    cin >> word;
    vector<string> pathString;
    wordBreak(word, pathString, dictionary, 0);
}


//test case
/*
6
micro soft microsoft hi ring hiring
microsofthiring


11
i like pep coding pepper eating mango man go in pepcoding
ilikepeppereatingmangoinpepcoding

*/