1. Combination sum

A. all solutions

    void dfs(vector<vector<int> >&res,vector<int> singleRes,int index,int target ,vector<int> &candidates){
        if(target==0){
            res.push_back(singleRes);
            return;
        }else if(target<0)
            return;
         
        for(int i = index;i<candidates.size();i++){
            singleRes.push_back(candidates[i]);
            dfs(res,singleRes,i,target-candidates[i],candidates);
            singleRes.pop_back();
        }
    }
    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        vector<vector<int> >res;
        sort(candidates.begin(),candidates.end());
        vector<int> singleRes;
        dfs(res,singleRes,0,target,candidates);
        return res;
    }

B, best solution

    public static int combinationSum(int[] num, int target){
        if (num == null || num.length == 0){
            return 0;
        }
        if (target == 0){
            return 0;
        }
        int[] dp = new int[target+1];
        dp[0] = 0;
        for (int i = 1; i <= target; i++){
            dp[i] = Integer.MAX_VALUE;
            for (int j = 0; j < num.length;j++){
                if (num[j] <= i && dp[i-num[j]]+1 < dp[i]){
                    dp[i] = dp[i-num[j]]+1;
                }
            }
        }
        return dp[target];
    }

2. Jump game

1. valid check

    bool canJump(vector<int> A) {
        // write you code here
        int maxV =0;
        int n = A.size();
        for(int i=0;i<n;i++){
            if(maxV>=n-1)
                return true;
            if(maxV== i&&A[i]==0)
                return false;
            maxV = max(maxV,i+A[i]);    
        }         
    }

 b. least jump

    int jump(vector<int> A) {
        // wirte your code here
        int n = A.size();
        int res = 0;
        int maxJump = 0,jump=0;
        int i=0,step = 0 ;
        while(i<=jump && i < n){
            if(i>maxJump){
                maxJump = jump;
                step++;
            }
            jump = max(jump,i+A[i]);
            i++;
        }  
        if(i<n-1)
            return 0;
        else
            return step;

    }

3.Unique Binary Search Trees

a. only number

    int numTrees(int n) {
        if(n<2)
            return n;
        int dp[n+1];
        memset(dp,0,(n+1)*sizeof(int));
        dp[0] = 1;
        dp[1] = 1;
        for(int i=2;i<=n;i++){
            for(int j=0;j<i;j++){
                dp[i] += dp[j]*dp[i-j-1];
            }
        }
        return dp[n];
    }

b. all solutions

    vector<TreeNode *> dfs(int left,int right){
        vector<TreeNode *> res;
 
        if(left>right){
            res.push_back(NULL);
            return res;
        }
         
        for(int k=left;k<=right;k++){
            vector<TreeNode *> lList = dfs(left,k-1);
            vector<TreeNode *> rList = dfs(k+1,right);
            for(int i=0;i<lList.size();i++){
                for(int j=0;j<rList.size();j++){
                    TreeNode *tmp = new TreeNode(k);
                    tmp->left = lList[i];
                    tmp->right = rList[j];
                    res.push_back(tmp);
                }
            }
        }
        return res;
    }
    vector<TreeNode *> generateTrees(int n) {   
        return dfs(1,n);
    }

4. Word Search

a. valid check

   bool dfs(vector<vector<char> > &board,int i,int j, string word,int index,vector<vector<bool> > &used){
       if(index == word.length()){
           return true;
       }
         
        int row = board.size();
        int col = board[0].size();
         
        // sequence is important.
        if(i<0 || i>row-1 || j<0 || j>col-1 ||used[i][j] ||  board[i][j]!= word[index])
            return false;
             
        used[i][j] = true;
         
        bool result = dfs(board,i-1,j,word,index+1,used)
                    ||dfs(board,i+1,j,word,index+1,used)
                    ||dfs(board,i,j-1,word,index+1,used)
                    ||dfs(board,i,j+1,word,index+1,used);
                     
        used[i][j] = false;             
       return result;  
   }
 
    bool exist(vector<vector<char> > &board, string word) {
        int row = board.size();
        int col = board[0].size();
        vector<vector<bool> >used(row,vector<bool>(col,false));
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++)
                if(board[i][j]== word[0] && dfs(board,i,j,word,0,used)){
                    return true ;
                }
        }
        return false;
    }

b. all solutions

 

5. Path Sum

a. valid check

    bool hasPathSum(TreeNode *root, int sum) {
        if(!root)
            return false;
        else if(!root->left && !root->right)
            return sum==root->val;
        else
            return hasPathSum(root->left,sum-root->val)||
                hasPathSum(root->right,sum-root->val);
             
    }

b. all solutions

    void dfs(vector<vector<int> > &res,vector<int> singleRes,int sum,TreeNode *root){
        if(!root->left && !root->right && sum==root->val){
            singleRes.push_back(root->val);
            res.push_back(singleRes);
            return;
        }
        singleRes.push_back(root->val);
        if(root->left)
            dfs(res,singleRes,sum-root->val,root->left);
        if(root->right)
            dfs(res,singleRes,sum-root->val,root->right);
    }
    vector<vector<int> > pathSum(TreeNode *root, int sum) {
        vector<vector<int> > res;
        vector<int> singleRes;
        if(!root)
            return res;
 
        dfs(res,singleRes,sum,root);
        return res;
    }

6. Palindrome Partitioning

a. all solutions

    bool isPalindrome(string &s,int l,int r){
        while(l<r){
            if(s[l]!=s[r])
                return false;
            else{
                l++;
                r--;
            }     
        }
        return true;
    }
     
    void dfs(vector<vector<string>> &res, vector<string> singleRes,int index,string &s){
        if(index==s.length()){
            res.push_back(singleRes);
            return;
        }
         
        for(int i=index;i<s.length();i++){
            if(isPalindrome(s,index,i)){
                singleRes.push_back(s.substr(index,i-index+1));
                dfs(res,singleRes,i+1,s);
                singleRes.pop_back();
            }
        }
    }
     
    vector<vector<string>> partition(string s) {
        vector<vector<string>> res;
        vector<string> singleRes;
        dfs(res,singleRes,0,s);
        return res;
    }

b. best solution

    int minCut(string s) {
       int len = s.length();
       bool dp[len][len];
       memset(dp,0,len*len*sizeof(bool));
       int res[len+1];
       for(int i=0;i<=len;i++)
            res[i] = len-i;
             
        for(int i=len-1;i>=0;i--){
            for(int j=i;j<len;j++){
                dp[i][j] = (s[i]==s[j] &&(j-i<2 ||dp[i+1][j-1]));
                 
                if(dp[i][j])
                    res[i] = min(res[i],res[j+1]+1);
            }
        }
        return res[0]-1;
    }

7.Word Break

a. valid check

    bool wordBreak(string s, unordered_set<string> &dict) {
        int len = s.length();
        if(!len)
            return true;
             
        bool *dp = new bool[len];
        memset(dp,0,len*sizeof(bool));
 
        for(int i=0;i<len;i++){
            if(dict.find(s.substr(0,i+1))!=dict.end()){
                dp[i] = true;
                continue;
            }
            for(int j=0;j<i;j++){
                if(dp[j] && dict.find(s.substr(j+1,i-j))!=dict.end()){
                    dp[i] = true;
                    break;
                }
            }
        }
         
        return dp[len-1];
    }

b. all solutions

    bool wordBreakable(string s, unordered_set<string> &dict) {
        int len = s.length();
        if(!len)
            return true;
         
        bool dp[len];
        memset(dp,0,sizeof(bool)*len);
         
        for(int i=0;i<len;i++){
            if(dict.find(s.substr(0,i+1))!=dict.end()){
                dp[i] = true;
                continue;
            }
             
            for(int j=0;j<i;j++){
                if(dp[j] && dict.find(s.substr(j+1,i-j))!=dict.end()){
                    dp[i] = true;
                    break;
                }
            }
        }     
        return dp[len-1];             
    }
 
    void dfs(vector<string> &res,string singleRes,int index,string s, unordered_set<string> &dict){
        if(index==s.length()){
            res.push_back(singleRes);
            return;
        }
        string tmp;
        for(int i=index;i<s.length();i++){
            tmp += s[i];
            if(dict.find(tmp)!=dict.end()){
                if(singleRes.empty())
                    dfs(res,singleRes+tmp,i+1,s,dict);
                else
                    dfs(res,singleRes+" "+ tmp,i+1,s,dict);
            }
        }
    }
 
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        vector<string> res;
        if(!wordBreakable(s,dict))
            return res;
             
        dfs(res,"",0,s,dict);     
        return res;     
    }

8.Word Ladder

a. best solution value

    int ladderLength(string start, string end, unordered_set<string> &dict) {
        queue<string> q;
        map<string,int>m;
        int len = start.length();
        q.push(start);
        m[start] = 1;
        int level = 1;
        while(!q.empty()){
            int cnt = q.size();
            while(cnt--){
                string s = q.front();
                q.pop();
                for(int i=0;i<len;i++){
                    for(char j='a';j<='z';j++){
                        char tmp = s[i];
                        s[i] = j;
                        if(s==end)
                            return level+1;
                        if(dict.find(s)!=dict.end() &&!m[s])
                            q.push(s),m[s]=1;
                             
                        s[i] = tmp;
                    }
                }
            }
            level++;
        }
        return 0;
    }

b. all best solution

    vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
        vector<vector<string>> res;
        dict.insert(start);
        dict.insert(end);
         
        unordered_map<string,vector<string>> paths;
        vector<string> init;
        for(unordered_set<string>::iterator it=dict.begin();it!=dict.end();it++)
            paths[*it]=init;
         
        vector<unordered_set<string>>layer(2);
        int pre=0;
        int cur=1;
         
        layer[cur].insert(start);
        while(1){
            pre = !pre;
            cur = !cur;
             
            for(unordered_set<string>::iterator it=layer[pre].begin();it!=layer[pre].end();it++)
                dict.erase(*it);
             
            layer[cur].clear();
         
         
            for(unordered_set<string>::iterator it=layer[pre].begin();it!=layer[pre].end();it++){
                for(int i=0;i<(*it).size();i++){
                    string tmp = *it;
                    for(char j='a';j<='z';j++){
                        if(tmp[i]==j)
                            continue;
                        tmp[i] = j;
                        if(dict.find(tmp)!=dict.end()){
                            layer[cur].insert(tmp);
                            paths[tmp].push_back(*it);
                        }
                    }
                }
            }
            if(layer[cur].empty())
                return res;
            if(layer[cur].find(end)!=layer[cur].end())
                break;
        }
        vector<string> singleRes;
        generatePath(res,singleRes,paths,end);
        return res;
    }
     
    void generatePath(vector<vector<string>> &res,vector<string> singleRes,
        unordered_map<string,vector<string>> &paths,string end){
        if(paths[end].empty()){
            singleRes.push_back(end);
            reverse(singleRes.begin(),singleRes.end());
            res.push_back(singleRes);
            return;
        }
        singleRes.push_back(end);
         
        for(vector<string>::iterator it=paths[end].begin();it!=paths[end].end();it++)
            generatePath(res,singleRes,paths,*it);
             
        singleRes.pop_back();     
    }