Word break: Get all the possible sentences

Problem: Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

Example: (Taken from leetcode)

Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
  "cats and dog",
  "cat sand dog"
]

Approach: Recursion with memorization. Memorization is introduced just for more efficient solution then usual backtracking.

        public static IList<string> WordBreakAllPatitions(string s, IList<string> wordDict)

        {

            Dictionary<string, List<string>> resultsHash = new Dictionary<string, List<string>>();

            return WordBreakAllPatitionsDP(s, wordDict, resultsHash);

        }

        private static List<string> WordBreakAllPatitionsDP(string s, IList<string> wordDict, Dictionary<string, List<string>> resultsHash)

        {

            List<string> result = new List<string>();

            if (resultsHash.ContainsKey(s))

            {

                return resultsHash[s];

            }

            if (s.Length == 0)

            {

                return new List<string> { string.Empty };

            }

            foreach (string word in wordDict)

            {

                if (s.StartsWith(word))

                {

                    List<string> currResult = WordBreakAllPatitionsDP(s.Substring(word.Length), wordDict, resultsHash);

                    foreach(string str in currResult)

                    {

                        string mid = (str == "") ? "" : " ";

                        result.Add(word + mid + str);

                    }

                }

            }

            resultsHash.Add(s, result);

            return result;

        }