I found this question here but I don't think the answer is correct. Here is the original word break question:Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.Return all such possible sentences.For example, given s = catsanddog, dict = [cat, cats, and, sand, dog].A solution is [cats and dog, cat sand dog].One way to do it is to use backtracking:vector<string> wordBreak(string s, vector<string>& wordDict) {    vector<string> sentences;    string prefix = ;    findWords(prefix, 0, s, wordDict, sentences);    return sentences;}void findWords(string prefix, int start, const string s, const vector<string> &wordDict, vector<string> &sentences) {    if (start == s.size()) {        sentences.push_back(prefix);        return;    }    for (int i = start; i < s.size(); i++) {        string word = s.substr(start, i - start + 1);        if (find(wordDict.begin(), wordDict.end(), word) != wordDict.end()) {            string new_prefix = prefix ==  ? word : prefix +   + word;            findWords(new_prefix, i + 1, s, wordDict, sentences);        }    }}In the worst case, the dictionary contains all prefix of s. From my understanding, in this case, the time complexity is T(n) = T(n-1) + T(n-2) + ... + T(1) = 2T(n-1) = O(2^n)I'm not sure if this is correct because I see some threads say it is O(n^n)?The other way is to use backtracking with memorization:vector<string> wordBreak(string s, vector<string>& wordDict) {    return constructSentences(0, s, wordDict);}// Return all sentences that can be constructed using substring s[start, ...]vector<string> constructSentences(int start, const string s, const vector<string> &wordDict) {    if (dict.count(start)) {        return dict[start];    }    vector<string> sentences;    if (start == s.size()) {        sentences.push_back();        return sentences;    }    for (int i = start; i < s.size(); i++) {        string word = s.substr(start, i - start + 1);        if (find(wordDict.begin(), wordDict.end(), word) != wordDict.end()) {            vector<string> subsentences = constructSentences(i + 1, s, wordDict);            dict[i + 1] = subsentences;            for (const auto elem : subsentences) {                sentences.push_back(elem ==  ? word : word +   + elem);            }        }    }    return sentences;}I'm not sure how to analyze the time complexity of this approach since some subproblem can be solved in constant time by dictionary lookup but some cannot.Furthermore, I'm not sure how to analyze the space complexity of these two approaches. From my understanding, the space is bounded by the final output. Since we have O(2^n) final sentence and each sentence have size O(n), does it mean the space complexity for both approach is O(2^n * n) ? 
time complexity of word break algorithm
algorithm analysis;runtime analysis;backtracking