原题链接： https://leetcode-cn.com/problems/word-break-ii/
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。
说明：
分隔时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
image.png
解题思路：
- 动态规划+回溯；
- 单独用回溯算会出现“超出时间限制”错误，因此先用动态规划判断
dp[-1]==True； - 如果可以拆分，再使用回溯计算结果，否则返回
[]。
Python3代码：
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
size = len(s)
dp = [False for i in range(size+1)]
dp[0] = True
word_set = set(wordDict)
for i in range(1,size+1):
for j in range(i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
break
res = []
if dp[-1]:
def func(begin, track):
if len(''.join(track))==size:
res.append(' '.join(track))
return
for i in range(begin, size):
if s[begin:i+1] in word_set:
func(i+1, track+[s[begin:i+1]])
func(0, [])
return res
