// Bottom up - directly storing all combinations for string starting at i
public class Solution {
    public IList<string> WordBreak(string s, IList<string> dict) {
        
        List<string>[] dp = new List<string>[s.Length+1];
        var set = new HashSet<string>(dict);
        for(int i=0;i<dp.Length;i++){
            dp[i] = new List<string>();
        }
        for(int i=s.Length-1;i>=0;i--){  // dp[i] means starting at i, we have calculated all dp[x] x>i
            var res = new List<String>();
            for(int k=i; k<s.Length;k++){ // Breaking at k 
                if((k+1==s.Length || dp[k+1].Count>0)){
                    var word = s.Substring(i, k-i+1);
                    if(!set.Contains(word)){
                        continue;
                    }
                    if(k+1==s.Length){
                        res.Add(word);
                    }
                    else{
                        foreach(var x in dp[k+1]){
                            res.Add(word+" " + x);
                        }
                    }
                }
            }
            
            dp[i] = res;
        }
     
        return dp[0];
    }
}

// Bottom-up Fill the dp table with parent pointers and then do dfs to generate string from parent pointers
public class Solution {
    List<String> res;
    public IList<string> WordBreak(string s, IList<string> dict) {
        res = new List<String>();
        List<int>[] dp = new List<int>[s.Length+1];
        for(int i=0;i<dp.Length;i++){
            dp[i] = new List<int>();
        }
        
        var set = new HashSet<string>(dict);
        for(int i=s.Length-1;i>=0;i--){  // dp[i] means starting at i, we have calculated all dp[x] x>i
            for(int k=i; k<s.Length;k++){
                if((k+1==s.Length || dp[k+1].Count>0) && set.Contains(s.Substring(i, k-i+1))){
                    dp[i].Add(k+1);
                }
            }
        }
        
        //Console.WriteLine(string.Join(',', dp.Select(x=>string.Join('|', x.ToArray())).ToArray()));
        dfs(s, dp, 0, new StringBuilder());
        return res;
    }
    
    public void dfs(string s, List<int>[] dp, int i, StringBuilder sb){
        if(i==s.Length){
            sb.Length--; //for ignoring last space
            res.Add(sb.ToString());
            return;
        }
        
        foreach(var j in dp[i]){
            int len = sb.Length;
            sb.Append(s.Substring(i, j-i)).Append(' ');
            dfs(s, dp, j, sb);
            sb.Length = len;
        }
    }
}

// TOP - Down : If dictionary is small
public class Solution {
    Dictionary<string, List<string>> map; 
    public IList<string> WordBreak(string s, IList<string> dict) {
        map = new Dictionary<string, List<string>>();
        return dfs(s, dict);
    }
    
    public List<string> dfs(string s, IList<string> dict){ // for remaining string till end
        if(map.ContainsKey(s)){
            return map[s];
        }
        
        var res = new List<String>();
        foreach(var w in dict){
            if(s.StartsWith(w)){
                if(s.Length==w.Length){
                    res.Add(w);
                    continue;
                }
                string rem = s.Substring(w.Length);
                var subRes = dfs(rem, dict);
                foreach(var sub in subRes){
                    res.Add(w + " " + sub);
                }
            }
        }
        
        map[s]= res;
        return res;
    }
}

// Top - Down : If dictionary is large
public class Solution {
    Dictionary<string, List<string>> map; 
    HashSet<string> set;
    public IList<string> WordBreak(string s, IList<string> dict) {
        map = new Dictionary<string, List<string>>();
        set = new HashSet<string>(dict);
        return dfs(s);
    }
    
    public List<string> dfs(string s){ // for remaining string till end
        if(map.ContainsKey(s)){
            return map[s];
        }
        
        var res = new List<String>();
        for(int i = 1; i<= s.Length; i++){
            string w = s.Substring(0,i);
            if(set.Contains(w)){
                if(i==s.Length){
                    res.Add(w);
                    continue;
                }
                string rem = s.Substring(w.Length);
                var subRes = dfs(rem);
                foreach(var sub in subRes){
                    res.Add(w + " " + sub);
                }
            }
        }
        
        map[s]= res;
        return res;
    }
}