using System.Collections.Generic;
public static Dictionary<string,List<string>> map;
public static void Main()
Console.WriteLine("Hello World");
List<string> dict = new List<string>();
map = new Dictionary<string,List<string>>();
var list = DFS("catsanddog",dict,0);
foreach(var item in list)
private static List<string> DFS(string s, List<string> dict,int level)
if ( map.ContainsKey(s) )
List<string> ret = new List<string>();
for(int i = s.Length-1;i>=0;i--)
string temp = s.Substring(i);
if ( dict.Contains(temp))
List<string> strs = DFS(s.Substring(0,i),dict,level+1);
foreach(var item in strs)
ret.Add(item + " " + temp);
Console.WriteLine(s + " Level " + level + " " + ret.Count);