44 回溯算法解单次拆分II

问题描述：给定一个非空字符串s和一个包含非空单次的词典wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单次都在词典中，返回这些所有可能的句子。

回溯算法求解：dfs算法中用一个index记录当前所在非空字符串的位置，并遍历位置后的所有元素，倘若当前元素与后续元素出现在wordDict中，则加入临时链表中，更新index进入下一个dfs中，当这个函数退出时，去除这个元素，并进入新一次的循环判断中；

public void dfs(String s,int index,List<String>wordDict,List<List<String>>res,ArrayList<String>templist)
{

if(index==s.length())
{
res.add(new List<String>(templist));
return;
}
for(int i=index;i<s.length();i++)
{
if(wordDict.contains(s.substring(index,i+1)))
{
templist.add(s.substring(index,i+1));
dfs(s,i+1,wordDict,res,templist);
templist.remove(templist.size()-1);
}else
{
continue;
}
}
}
public List<List<String>> dfs(String s,List<String>wordDict)
{
List<List<String>>list=new LinkedList<LinkedList<String>>res;
dfs(s,0,wordDict,res,new ArrayList<String>());
???????return list;
}