# 0140. Word Break II
###### tags: `Leetcode` `Hard` `DFS`
Link: https://leetcode.com/problems/word-break-ii/
## 思路 O(N * 2^N)
用一个function去找每个s能拆解出的所有可能的字符串，然后存进map里面
(可以用memo剪枝 但没写)
## Code

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        List<String> ans = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        backtracking(ans, sb, s, wordDict);
        return ans;
    }
    private void backtracking(List<String> ans, StringBuilder sb, String s, List<String> wordDict){
        int len = sb.length();
        if(s==""){
            ans.add(sb.toString());
        }
        else{
            for(String word:wordDict){
                if(s.startsWith(word)){
                    if(sb.length()!=0) sb.append(" ");
                    backtracking(ans, sb.append(word), s.substring(word.length()), wordDict);
                    sb.setLength(len);
                }
            }
        }
    }
}