solution.h

/*
Code generated by https://github.com/goodstudyqaq/leetcode-local-tester
*/
#if __has_include("../utils/cpp/help.hpp")
#include "../utils/cpp/help.hpp"
#elif __has_include("../../utils/cpp/help.hpp")
#include "../../utils/cpp/help.hpp"
#else
#define debug(...) 42
#endif

class Solution {
   public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        set<string> S;
        for (auto it : wordDict) {
            S.insert(it);
        }        
        vector<string> ans;
        vector<string> now;
        int n = s.size();
        function<void(int)> dfs = [&](int idx) {
            if (idx == n) {
                string it = now[0];
                for (int i = 1; i < now.size(); i++) {
                    it += " " + now[i];
                }
                ans.push_back(it);
                return;
            }
            string tmp = "";
            for (int i = idx; i < n; i++) {
                tmp += s[i];
                if (S.count(tmp)) {
                    now.push_back(tmp);
                    dfs(i + 1);
                    now.pop_back();
                }
            }
        };
        dfs(0);
        return ans;
    }
};