Leetcode 140. Word Break II

class Solution {
public:
    vector<string> sentences;

    void wordBreakUtil(string s, int startIndex, vector<string> &curr,
                       vector<string>& wordDict) {

        // Base case
        if (startIndex == s.size()) {
            string currSentence = "";

            for (auto str : curr) {
                currSentence += str + ' ';
            }

            currSentence.pop_back();
            sentences.emplace_back(currSentence);

            return;
        }

        // Try to make a valid partition at all the indices for the current string
        for (int partitionIndex = startIndex; partitionIndex < s.size(); ++partitionIndex) {
            string t = s.substr(startIndex, partitionIndex - startIndex + 1);

            if (find(wordDict.begin(), wordDict.end(), t) != wordDict.end()) {
                curr.emplace_back(t);

                wordBreakUtil(s, partitionIndex + 1, curr, wordDict);

                curr.pop_back();
            }
        }
    }

    vector<string> wordBreak(string s, vector<string>& wordDict) {
        vector<string> curr;

        // Initially we consider the whole string 's'
        int startIndex = 0;

        wordBreakUtil(s, startIndex, curr, wordDict);

        return sentences;
    }
};