class Solution{
public:
    using vs = vector<string>; using um = unordered_map<string,bool>;
    void fun(int idx,um& dict, string& s, vs& ans,vs sentence, const int& n){
        if(idx == s.length()){
            string main;
            for(auto word : sentence)
                main += word + ' ';
            main.pop_back();
            ans.push_back(main);
            return;
        }
        string temp = "";
        for(int i = idx; i < s.length(); i++){
            temp.push_back(s[i]);
            if(dict[temp]){
                sentence.push_back(temp);
                fun(i+1, dict, s, ans, sentence, n);
                sentence.pop_back();
            }
        }
    }
    vector<string> wordBreak(int n, vector<string>& d, string s)
    {
        // code here
        um dict;
        for(auto word : d)
            dict[word] = true;
        vs ans;
        vs sentence;
        fun(0, dict, s, ans, sentence, n);
        return ans;
    }
};

class Solution{
    public:
    void findPaths(int i, int j, vector<string>& paths ,string path, vector<vector<int>>& mat){
        if(i == mat.size()-1 && j == mat.size()-1)
        {
            paths.push_back(path);
            return;
        }
        int dx[4] = {0,1,0,-1};
        int dy[4] = {1,0,-1,0};
        char move[4] = {'R','D','L','U'};
        mat[i][j] = 0;
        for(int k = 0; k < 4; k++){
            int x = i + dx[k], y = j+ dy[k];
            if((x>=0 && x < mat.size() && y >= 0 && y < mat.size()) && mat[x][y] != 0){
                
                path.push_back(move[k]);
                findPaths(x, y, paths, path, mat);
                path.pop_back();
            }
        }
        mat[i][j] = 1;
    }
    vector<string> findPath(vector<vector<int>> &mat, int n) {
        // Your code goes here
        vector<string> paths;
        string path;
        if(mat[0][0] == 0)
            return paths;
        findPaths(0, 0, paths, path, mat);
        // sort(paths.begin(), paths.end());
        return paths;
        
    }
};

    void print(vector<int>& v){
        for(auto ele : v)
            cout << ele << " ";
        cout<< endl;
    }
    void backtrack(int index, vector<int> ans){
        if(index == (ans.size() - 1)){
            print(ans);
            return;
        }
        for(int i = index; i < ans.size(); i++){
            swap(ans[index], ans[i]);
            backtrack(index+1, ans);
            swap(ans[index], ans[i]);
        }
    }