leet_140

题目： 原题链接

这道题和139其实是一样的，唯一的区别是，139只要求输出是否能够完成划分，而这道题要求打印出这些组合。

题解：

和139一样的DP，f[i]表示从S的第i个字符到末尾这个子串能否由dict构成。很显然，如果S[0..i-1]是dict中的一个字符串，那么问题成了判断子串S[i..last]是否可以由dict构成，递归一下就好了。判断S[0..i-1]是否是dict中的一个子串可以反过来，枚举dict，看dict[k]是不是S的前缀。

需要注意的是，139用一个辅助数组f[i]来表示S[i..last]是否可以完成划分，这里需要使用f[i]来表示S[i..last]如果可以完成划分，位置i可以选择哪些word。DP结束后用一次类似链表的遍历，把所有结果打印出来即可。