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:
    const int m = 1e9+7;
    using vvi = vector<vector<int>>;
    int countWays(int idx, int steps, int arrLen,vvi& dp){
        if(idx < 0 || idx >= arrLen)    return 0;
        if(steps == 0)
            if(idx != 0)  return 0;
            else return 1;
        if(dp[idx][steps] != -1)
            return dp[idx][steps];
        return dp[idx][steps] = ((countWays(idx,steps-1,arrLen,dp)%m + countWays(idx+1,steps-1,arrLen,dp)%m )%m+ countWays(idx-1,steps-1,arrLen,dp)%m)%m;
    }
    int numWays(int steps, int arrLen) {
        vvi dp;
        arrLen = min(steps/2+1,arrLen);
        dp.resize(arrLen + 1,vector<int>(steps+1, -1));
        return countWays(0, steps, arrLen,dp);
    }
};

git reset 89f6c3d --hard