Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

&nbsp;
Example 1:

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


Example 2:

Input: s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"]
Explanation: Note that you are allowed to reuse a dictionary word.


Example 3:

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


&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 20
	1 &lt;= wordDict.length &lt;= 1000
	1 &lt;= wordDict[i].length &lt;= 10
	s and wordDict[i] consist of only lowercase English letters.
	All the strings of wordDict are unique.


class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: List[str]
        """

        dic = defaultdict(list)
        for w in wordDict:
            dic[w[0]].append(w)
        result = []
        def recursion(idx , ans):
            if idx >= len(s):
                result.append(" ".join(ans))
                return

            for w in dic[s[idx]]:
                if s[idx : idx+len(w)] == w:
                    ans.append(w)
                    recursion(idx+len(w), ans)
                    ans.pop()

            return
        recursion(0, [])
        return result
class Solution {
	List<String> res = new ArrayList<>();
	String s;
	int index = 0;
	Set<String> set = new HashSet<>();
    public List<String> wordBreak(String s, List<String> wordDict) {
        this.s = s;
		for (String word: wordDict) set.add(word);
		backtrack("");
		return res;
    }
	public void backtrack(String sentence) {
	    if (index == s.length()) {
	        res.add(sentence.trim());
	        return;
        }
        int indexCopy = index;
        for (int i = index + 1; i <= s.length(); i++) {
	        String str = s.substring(index, i);
	        if (set.contains(str)) {
	            index = i;
	            backtrack(sentence + " " + str);
	            index = indexCopy;
            }
        }
        return;
    }
}
class Solution {
public:
    void helper(string s, unordered_set<string>& dict,int start, int index,string current,vector<string>& ans){
        if(start==s.size()){
            ans.push_back(current);
            return;
        }
        if(index==s.size()) return;

        string sub=s.substr(start,index-start+1);

        if(dict.count(sub)>0){
            string recursion;
            if(current.size()==0) recursion=sub;
            else recursion=current+" "+sub; 
            helper(s,dict,index+1,index+1,recursion,ans);
        }
        helper(s,dict,start,index+1,current,ans);
        return;
    }
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict;
        for(int i=0;i<wordDict.size();i++){
                dict.insert(wordDict[i]);
        }
        vector<string> ans;
        helper(s,dict,0,0,"",ans);
        return ans;
        
    }
};
var wordBreak = function(s, wordDict) {
    const n = s.length;
    const result = [];

    const findValidSentences = (currentString = '', remainingString = s, currentIndex = 0) => {
        if(currentIndex === remainingString.length) {
            if(wordDict.includes(remainingString)) {
                result.push(`${currentString} ${remainingString}`.trim())
            }
            return result;
        }

        const newWord = remainingString.slice(0, currentIndex);
        if(wordDict.includes(newWord)) {
            const newCurrentString = `${currentString} ${newWord}`;
            const newRemainingString = remainingString.slice(currentIndex);
            findValidSentences(newCurrentString, newRemainingString, 0);
        }

        return findValidSentences(currentString, remainingString, currentIndex + 1);
    }

    return findValidSentences();
};
Word Break II