[leetcode][**] Unique PathII

Follow up for "Unique Paths":

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,

There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.

Note: m and n will be at most 100.

My Code:

 
 int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
        int m = obstacleGrid.size();
        if(m == 0) return 0;
        int n = obstacleGrid[0].size();
        if(n == 0) return 0;
        int table[m][n];
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(obstacleGrid[i][j] == 1) {
                    table[i][j] = 0;
                    continue;
                }
                if(i == 0 && j == 0) 
                    table[i][j] = 1;
                else if(i == 0 && j != 0){
                    table[i][j] = table[i][j-1];
                } 
                else if(i != 0 && j == 0) {
                        table[i][j] = table[i-1][j];
                }
                else{
                    table[i][j] = table[i-1][j]+table[i][j-1];
                }
            }
        }
        return table[m-1][n-1];
    }

[leetcode][*]Unique Paths

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

int uniquePaths(int m, int n) {
        int table[n][m];
        if(m == 0 || n == 0) return 0;
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < m; ++j){
                if(i == 0 && j == 0) table[i][j] = 1;
                else if(i == 0 && j != 0) table[i][j] = table[i][j-1];
                else if(i != 0 && j == 0) table[i][j] = table[i-1][j];
                else{
                    table[i][j] = table[i-1][j]+table[i][j-1];
                }
            }
        }
        return table[n-1][m-1];
    }

[leetcode][****] Simplify Path

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

1. If the train of thought if not clear, this problem is hard.
2. /. does nothing;  /.. will get you back to the upper directory;
Algorithm:
1. delete the repeated "/".
2. add a "/" back to pair up all the "/"s.
3. only "/." and "/.." is considered seperatedly.
4. flag to mark the second "/" and handle the pop or push of stacks.

My Code:

  string simplifyPath(string path) {
       string ret = "";
       //erase "//"
       for(int i = path.length() - 1; i >=0; --i){
           if(path[i]==path[i+1] && path[i] == '/'){
               path.erase(i,1);
           }
       }
       //add "/" to the end to make sure "/" are in pairs
       if(path[path.length() - 1] != '/')
          path += '/';
       stack<string> cur;
       int flag = 0;
       string str = "";
       for(int i = 0; i < path.length(); ++i){
           if(path[i] == '/') ++flag;
           if(flag == 1) str += path[i];
           else if(flag == 2){
               if(str == "/.." && !cur.empty())
                    cur.pop();
               if(str != "/." && str!="/.." )
                    cur.push(str);
               flag = 1;
               str = "/";
           }
       }
       while(!cur.empty()){
            ret = cur.top()+ret;
            cur.pop();
       }
       if(ret.empty()) return "/";
       return ret;
    }

[leetcode][***] Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

bool isNumber(string a){
        if(a.empty()) return false;
        int i = 0;
        if(a.length() == 1){
            return a[0] >= '0' && a[0] <= '9';
        }
        if(a[0] == '-'|| a[0] == '+') ++i;
        for(; i<a.length(); ++i){
            if(a[i]<'0' || a[i] >'9') return false;
        }
        return true;
    }
    int str2num(string a){
        if(a.empty()) return 0;
        int ret = 0;
        bool neg = false;
        int i = 0;
        if(a[0] == '-') {
            neg = true;
            ++i;
        }
        else if(a[0] == '+') {
            neg = false;
            ++i;
        }
        for(; i < a.length(); ++i){
            ret = ret*10+(a[i]-'0');
        }
        if(neg) return -ret;
        return ret;
    }
    int evalRPN(vector<string> &tokens) {
        if(tokens.empty()) return 0;
        stack<string> s1;
        stack<int> s2;
        for(int i = tokens.size() - 1; i >= 0; --i)
            s1.push(tokens[i]);
        while(!s1.empty()){
            string cur = s1.top();
            s1.pop();
            if(isNumber(cur)){
                int curnum = str2num(cur);
                s2.push(curnum);
            }
            else{
                int b = s2.top();
                s2.pop();
                int a = s2.top();
                s2.pop();
                int res;
                switch(cur[0]){
                    case('+'): res = a+b; break;
                    case('-'): res = a-b; break;
                    case('*'): res = a*b; break;
                    case('/'): res = a/b; break;
                    default: break;
                }
                s2.push(res);
            }
        }
        return s2.top();
    }

[leetcode][****] Letter Combinations

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

Basics:

1. string construction from char. string s(size_t n, char c).(Fills the string with n consecutive copies of character c.)

2. Switch: 

switch(variable){
  case(xx): xxx; break;
  ....
  default: xxx;
}

Algorithm:

Recursion Solve the problem.

My Code

string getChars(char a){
        switch(a){
        case('0'): return " ";
        case('2'): return "abc";
        case('3'): return "def";
        case('4'): return "ghi";
        case('5'): return "jkl";
        case('6'): return "mno";
        case('7'): return "pqrs";
        case('8'): return "tuv";
        case('9'): return "wxyz";
        default: return "";
    }
 }
    vector<string> RBuild(vector<string> str){
        vector<string> ret;
        if(str.empty()) return ret;
        string cur = str[0];
        str.erase(str.begin());
        vector<string> nxt = RBuild(str);
        if(nxt.empty()){
            for(int i = 0; i < cur.size(); ++i){
                string a(1, cur[i]);
                ret.push_back(a);
            }
            return ret;
        }else{
            for(int i = 0; i < cur.size(); ++i){    
                for(int j = 0; j < nxt.size(); ++j){
                    string a = cur[i]+nxt[j];
                    ret.push_back(a);
                }
            }
            return ret;
        }
    }
    vector<string> letterCombinations(string digits) {
        vector<string> ret;
        if(digits.empty()) {
            ret.push_back("");
            return ret;
        }
        vector<string> v;
        for(int i = 0; i < digits.length(); ++i){
            string str = getChars(digits[i]);
            if(str != ""){
                v.push_back(str);
            }
        }
        ret = RBuild(v);
        return ret;
       
    }

[leetcode][**] Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

My Code:

 void bfs(int start,int end, int k, vector<int> &current, vector<vector<int> > &res){
        if(end - start + 1 < k) return;
        if(k == 0){
            res.push_back(current);
            return;
        }
        for(int i = start; i <= end; ++i){
            current.push_back(i);
            bfs(i+1, end, k-1, current, res);
            current.pop_back();
        }
    }
    vector<vector<int> > combine(int n, int k) {
        vector<vector<int>> res;
        if(n < k) return res;
        vector<int> current;
        bfs(1, n, k, current, res);
        return res;
    }

[leetcode][*]

 bool validchar(char a){
        if(a >= '0' && a <= '9' || a >='a' && a <='z' || a >= 'A' && a <= 'Z')
            return true;
        else
            return false;
    }
    bool mequal(char a, char b){
        if((a - 'a' == b - 'a') || (a - 'a' == b - 'A') 
           ||(a - 'A' == b - 'a') || (a - 'A' == b - 'A'))
           return true;
        else
            return false;
    }
    bool isPalindrome(string s) {
        if(s.empty()) return true;
        int r = 0;
        int l = s.length() - 1;
        while(r < l){
            while(!validchar(s[r]) && r < l){
                ++r;
            }
            while(!validchar(s[l]) && r < l){
                --l;
            }
            if(!mequal(s[r], s[l])){
                return false;
            }else{
                ++r;
                --l;
            }
        }
        return true;
    }

[leetcode][***] Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

Algorithm:

1. unordered_set is needed to be the hashtable.

2. for each one check the whole consecutive sequence containing it. and on each check delete the checked ones.

My Code:

int longestConsecutive(vector<int> num) {
        // use unordered_set to insert and find for constant.
        unordered_set<int> numset;
        for(int i = 0; i < num.size(); ++i)
            numset.insert(num[i]);
        int len = 1;
        for(int i = 0; i < num.size(); ++i){
            int u = num[i];
            int v = u;
            int count = 1;
            if(numset.find(v)!=numset.end()){
                numset.erase(v);
                while(numset.find(--v)!=numset.end()){
                    numset.erase(v);
                    ++count;
                }
                v = u;
                while(numset.find(++v)!=numset.end()){
                    numset.erase(v);
                    ++count;
                }
                if(count < len){
                    len = count;
                }
            }
            
        }
        return len;
    }

[leetcode][***] Unique Tree

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

This is a DP problem.

In Order, n = 0, result = 1:

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

[leetcode][***] Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

C++ wont initialize automatically for you!!!

Idea:

1. Inorder traversal and see if it is in the increasing order.

First Code(Run Time Error at first)：The problem is that I should initialize the pre pointer to NULL!

bool isValidBST(TreeNode *root) {
        if(!root) return true;
        stack<TreeNode*> s;
        TreeNode* temp = root;
        TreeNode* pre = NULL;
        TreeNode* cur;
        while(temp){
            s.push(temp);
            temp = temp->left;
        }
        while(!s.empty()){
            cur = s.top();
            if(pre)
                if(pre->val >= cur->val) return false;
            pre = cur;
            s.pop();
            if(cur->right){
                cur = cur->right;
                while(cur){
                    s.push(cur);
                    cur = cur->left;
                }
            }
        }
        return true;
    }

[leetcode][****] LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Key Idea:

1. Here we need a queue to dequeue the least recently item. However as we need the randomly access of the items for set and get, queue in C++ STL will not meet the standard. Then, we need a doubly linked list to build the queue.

2. In the doubly linked list, we should have key, value, pre, and nxt in the list node.

3. In order to find the node via the key each time fast, we need a hashmap, in C++, we could use

map<int, QNode*>.

4. When get(key) called, the position of the node if existed should moved to the last as well.

5. When set(key, val) called, if existed, then change value and move to the last, pay attention for one node list and if current is on front or rear node; if not existed, check if full or not, if full, dequeue; then insert to the last node.

SHOULD ALWAYS PAY ATTENTION TO THE SPECIAL CASES: only one node, current is front or last.

struct QNode{
    int key;
    int value;
    QNode* pre;
    QNode* nxt;
    QNode(int k, int val){key = k; value = val;}
};
struct Queue{
    // current count of contents.
    int count;    
    // total capacity
    int numofnode;
    QNode* front;
    QNode* rear;
    Queue(int n){
        count = 0;
        numofnode = n;
        front = rear = NULL;
    }
    bool IsQueueFull(){
        return count == numofnode;
    }
    bool IsQueueEmpty(){
        return rear == NULL;
    }
    void Dequeue(){
        if(IsQueueEmpty()) return;
        //if only one node in the queue
        if(front == rear){
            delete front;
            front = NULL;
            rear = NULL;
            count = 0;
            return;
        }
        QNode* temp = front;
        front = temp->nxt;
        front->pre = NULL;
        delete temp;
        --count;
    }
    void Enqueue(QNode* node){
        if(IsQueueFull())
            Dequeue();
        if(IsQueueEmpty()){
            node->nxt = NULL;
            node->pre = NULL;
            front = node;
            rear = node;
            count = 1;
            return;
        }
        rear->nxt = node;
        node->pre = rear;
        node->nxt = NULL;
        rear = node;
        ++count;
    }
};

class LRUCache{
public:
    
    LRUCache(int capacity) {
        LRUqueue = new Queue(capacity);
    }
    
    int get(int key) {
        QNode* cur = LRUmp[key];
        //if current key is not in the map
        if(!cur) return -1;
        else{
            if(LRUqueue->front != LRUqueue->rear){
                if(cur == LRUqueue->rear){
                    return cur->value;
                }
                if(cur == LRUqueue->front){
                    LRUqueue->front = cur->nxt;
                }else{
                    cur->pre->nxt = cur->nxt;
                    cur->nxt->pre = cur->pre;
                }
                LRUqueue->rear->nxt = cur;
                cur->pre = LRUqueue->rear;
                cur->nxt = NULL;
                LRUqueue->rear = cur;
            }
            return cur->value;
        }
    }
    
    void set(int key, int value) {
        QNode* cur = LRUmp[key];
        // if not in the map, we need to insert to the queue and the map.
        if(!cur){
            cur = new QNode(key, value);
            //check if the queue is full
            if(LRUqueue->IsQueueFull()){
                LRUmp.erase(LRUqueue->front->key);
                //enqueue the current value.
                LRUqueue->Enqueue(cur);
                LRUmp[key] = cur;
            }else{
                LRUqueue->Enqueue(cur);
                LRUmp[key] = cur;
            }
        }else{
            // if the key->node is in the map and queue
            if(LRUqueue->front != LRUqueue->rear){
                if(cur == LRUqueue->rear){
                    cur->value = value;
                    LRUmp[key] = cur;
                    return;
                }
                if(cur == LRUqueue->front){
                    LRUqueue->front = cur->nxt;
                }else{
                    cur->pre->nxt = cur->nxt;
                    cur->nxt->pre = cur->pre;
                }
                LRUqueue->rear->nxt = cur;
                cur->pre = LRUqueue->rear;
                cur->nxt = NULL;
                LRUqueue->rear = cur;
            }
            cur->value = value;
            LRUmp[key] = cur;
        }
        
    }
private:
    Queue* LRUqueue;
    map<int, QNode*> LRUmp;
};

[leetcode][****] Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Algorithm:

This problem is very hard actually. The train of thought is that, %3. 

1) For every bit of each number, we should make the count of 1 mode 3. If repeated n times, then mode n.

2) As the result of %3 can be 0,1,2. Then the result should be kept in two bits instead of one. 

3) should think about for all one bit numbers as {a1, a2, ...., a3}. how to calculate 

    (a1 + a2 + a3+ ...+ an)%3 with bit operation. (&, |, ^). This is also hard to see. Then check the easier 

    problem of (a+b)%3. The truth table shoule be:

    a    b     results

    0   0      0    0

    0   1      0    1

    1   0      0    1

    1   1      1    0

[CareerCup] Given a node of Binary Tree.

[leetcode][**] Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Attention: 

from root to leaf distance 

               1

        2

   3        5

4

this distance is till 3 not 1. should find the nearest leaf!!

My Code:

int minDepth(TreeNode *root) {
        if(root == NULL) return 0;
        else if(root->left == NULL && root->right == NULL)
            return 1;
        else if(root->left == NULL && root->right != NULL)
            return 1 + minDepth(root->right);
        else if(root->right == NULL && root->left != NULL)
            return 1 + minDepth(root->left);
        else
            return 1 + std::min(minDepth(root->left), minDepth(root->right));
        }       

[twitter] Given an array with numbers, your task is to find 4 numbers that will satisfy this equation: A + B + C = D

Given an array with numbers, your task is to find 4 numbers that will satisfy this equation:
A + B + C = D

vector<int> find3sum(vector<int> &num, int target){
    vector<int> res1;
    for(int i = 0; i < num.size(); ++i){
        if(i && num[i] == num[i-1]) continue;
        int j = i+1;
        for(int k = num.size() -1; k > j; --k){
            if(k < num.size() -1 && num[k] == num[k+1]) continue;
            while(j < k && num[i] + num[j] + num[k] < target)
                 ++j;
            if(j < k && num[i] + num[j] + num[k] == target){
                int a[] = {num[i],num[j],num[k]};
                vector<int> res(a, a+3);
                return res;
            }
        }
    }
    return res1;
}
  
vector<int> findABCD(int a[], int n){
    vector<int> res;
    if(n < 0) return res;
    vector<int> num(a, a+n);
    sort(num.begin(), num.end());
    while(num.size() > 3){
        int target = num.back();
        num.pop_back();
        vector<int> res = find3sum(num, target);
        if(!res.empty()){
            res.push_back(target);
            return res;
        }
    }
    return res;
}

[twitter][*] Missing Number

You have n - 1 numbers from 1 to n. Your task is to find the missing number.

I.e.
n = 5
v = [4, 2, 5, 1]
The result is 3.

This is easy like sum them up and subtracted by (1+n)*n/2

My Code:

int findmissing(int a[], int n){

    int missing = 0;

    for(int i = 0; i < n; ++i){

        missing += a[i];

    }

    missing = (1+n+1)*(n+1)/2 - missing;

    return missing;

    }

[leetcode][*] Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Attention:

 XOR in C++ should be ^

 int singleNumber(int A[], int n) {

        if(n == 0) return 0;

        int ret = A[0];

        for(int i = 1; i < n; ++i)

            ret = ret ^ A[i];

        return ret;

    }

[leetcode][***] ThreeSum

 Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

Algorithm:
1. i is the first one, j is the second one, k is from last.
2. skip duplicated ones for i and k.
3. if num[i] > 0 or num[k] < 0, false.

My Code:

vector<vector<int> >threeSum(vector<int> &num) {
    sort(num.begin(), num.end());
    vector<int> ret;
    for (int i = 0; i < (int)num.size() && num[i] <= 0; ++ i) {
        if (i && num[i] == num[i - 1]) continue;
        int j = i + 1;
        for (int k = (int)num.size() - 1; k > j && num[k] >= 0; -- k) {
            if (k < (int)num.size() - 1 && num[k] == num[k + 1]) 
                continue;
            while (j < k && num[i] + num[j] + num[k] < 0) ++ j;
            if (j < k && num[i] + num[j] + num[k] == 0) {
                int a[] = {num[i], num[j], num[k]};
                ret.push_back(vector<int>(a, a + 3));
            }
        }
    }
    return ret;
}

[leetcode][*] Two Sum

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Things need to pay attention: 1) the index should + 1; 2) there may be same value contents, and index should not be the same; 3) index1 should > index2

Algorithm:

1. Sort the array and store in another array.

2. search the i and j.

3. find the index in the original array.

My Code:

    int findindex(int val, vector &num, int start){
        for(int i = start; i < num.size(); ++i){
            if(num[i] == val)
                return i;
        }
        return -1;
    }
    vector twoSum(vector &numbers, int target) {
        vector res;
        if(numbers.empty()) return res;
        vector sorted = numbers;
        sort(sorted.begin(), sorted.end());
        int i = 0;
        int j = sorted.size() - 1;
        while(i < j){
            int cur = sorted[i] + sorted[j];
            if(cur > target)
                --j;
            else if(cur < target)
                ++i;
            else{
                int aindex = findindex(sorted[i], numbers, 0);
                int bindex = findindex(sorted[j], numbers, 0);
                if(aindex == bindex){
                    bindex = findindex(sorted[j], numbers, aindex+1);
                }
                if(aindex < bindex){
                    res.push_back(aindex+1);
                    res.push_back(bindex+1);
                }else{
                    res.push_back(bindex+1);
                    res.push_back(aindex+1);
                }
                return res;
            }
        }
    }

[leetcode][**] Combination Sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a₁, a₂, … , a_k) must be in non-descending order. (ie, a₁ ≤ a₂ ≤ … ≤ a_k).
• The solution set must not contain duplicate combinations.

For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6] 

Algorithm:

1. This problem is the same as the previous one, we can use DFS and take the input as a tree.

2. Should be careful that the solution set must not contain duplicate combinations. 

3. remember to pop_back the path after each recursion finished.

My Code:

bool uniquesum(vector > res, vector check){
        for(int i = 0; i < res.size(); ++i){
            if(std::equal(res[i].begin(), res[i].end(), check.begin()))
                return false;
        }
        return true;
        
    }
    void dfs(int left, vector & num, int target, vector &path, vector > &res){
        if(!target) {
            if(uniquesum(res, path))
                res.push_back(path);
            return;
        }
        for(int i = left; i < num.size(); ++i){
            if(num[i] > target) break;
            path.push_back(num[i]);
            dfs(i+1, num, target-num[i], path, res);
            path.pop_back();
        }
        return;
    }

    vector > combinationSum2(vector &num, int target) {
        vector > res;
        if(num.empty()) return res;
        sort(num.begin(), num.end());
        vector path;
        dfs(0, num, target, path, res);
        return res;
    }

[leetcode] Combination Sum

vector<vector<int> > findcombination(vector<int> valid, int target){
        vector<vector<int> > res;
        int len = valid.size();
        if(len == 0) return res;
        //discard all the values larger than target.
        while(valid.back() > target){
            valid.pop_back();
            if(valid.empty()) return res;

        }
        int i = valid.size() - 1;
        while( i >= 0 ){
            int head = valid[i];
            int cur = head;
            valid.pop_back();
            vector<int> headvec;
            while(cur <= target){
                headvec.push_back(head);
                if(cur == target){
                    res.push_back(headvec);
                    break;
                }
                vector<vector<int> > tails = findcombination(valid, target - cur);
                for(int j = 0; j < tails.size(); ++j){
                    for(int k = 0; k < headvec.size(); ++k){
                        tails[j].push_back(headvec[k]);
                    }
                    res.push_back(tails[j]);
                }
                cur+=head;
            }
            --i;
        }
        return res;
}

    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        vector<vector<int> > res;
        if(candidates.empty()) return res;
        sort(candidates.begin(), candidates.end());
        res = findcombination(candidates, target);
        return res;
    }
=========================================================

    void dfs(int left, vector<int>& candidates, vector<int>& current, vector< vector<int> >& ret, int target) {
        if (!target) {ret.push_back(current); return;}
        for (int i = left; i < (int)candidates.size(); ++ i) {
            if (candidates[i] > target) break;
            current.push_back(candidates[i]);
            dfs(i, candidates, current, ret, target - candidates[i]);
            current.pop_back();
        }
    }

    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        vector< vector<int> > ret;
        vector<int> current;
        sort(candidates.begin(), candidates.end());
        dfs(0, candidates, current, ret, target);
        return ret;
    }

[leetcode] Minimum Path Sum *

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

My Code:

 int minPathSum(vector<vector<int> > &grid) {

        if(grid.empty()) return 0;

        int width = grid[0].size();

        int height = grid.size();

        int table[height][width];

        table[0][0] = grid[0][0];

        for(int i = 0; i < height; ++i){

            for(int j = 0; j < width; ++j){

                if(i == 0 && j != 0 )

                    table[0][j] = table[0][j-1]+grid[0][j];

                else if(j == 0 && i != 0)

                    table[i][0] = table[i-1][0]+grid[i][0];

                else if(i != 0 && j != 0){

                    table[i][j] = min(table[i-1][j], table[i][j-1]) + grid[i][j];

                }

            }

        }

        return table[height-1][width-1];

    }

[leetcode] Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

My Code:

 vector<vector<int> > pathSum(TreeNode *root, int sum) {

        vector<vector<int> > res;

        vector<int> path;

        if(!root) return res;

        if(!root->left && !root->right){

            if(root->val == sum){

                path.push_back(root->val);

                res.push_back(path);

                return res;

            }else{

                return res;

            }

        }else{

            if(root->left){

                vector<vector<int> > leftres = pathSum(root->left, sum - (root->val));

                for(int i = 0; i < leftres.size(); ++i){

                leftres[i].insert(leftres[i].begin(), root->val);

                res.push_back(leftres[i]);

                }

            }

            if(root->right){

                vector<vector<int> > rightres = pathSum(root->right, sum - (root->val));

                for(int i = 0; i < rightres.size(); ++i){

                    rightres[i].insert(rightres[i].begin(), root->val);

                    res.push_back(rightres[i]);

                }

            }

            return res;

        }

    }

Discuss

[leetcode] Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

My Code:

 bool hasPathSum(TreeNode *root, int sum) {

        if(!root) return false;

        queue<TreeNode*> q;

        q.push(root);

        while(!q.empty()){

            TreeNode* cur = q.front();

            if(!cur->left && !cur->right){

                if(cur->val == sum)

                    return true;

            }

            else{

                if(cur->left){

                    cur->left->val = cur->val + cur->left->val;

                    q.push(cur->left);

                }

                if(cur->right){

                    cur->right->val = cur->val + cur->right->val;

                    q.push(cur->right);

                }

            }

            q.pop();

        }

        return false;

    }