Word Break II

• Time : $O(|A|^2)$
• Space : $O(B)$

void helper(string& s, int p, string now, unordered_set<string>& us, vector<string>& res) {
    if(p == s.length()) {
        now.pop_back();
        res.push_back(now);
    } else {
        string build = "";
        for(int i = p; i < s.length(); i++) {
            build.push_back(s[i]);
            if(us.count(build)) helper(s,i+1,now + build + " ", us, res);
        }
    }
}
vector<string> Solution::wordBreak(string A, vector<string> &B) {
    unordered_set<string> us(begin(B), end(B));
    vector<string> res;
    helper(A,0,"", us, res);
    return res;
}