[LeetCode]Combination Sum IV

A slow one:

class Solution {  
public:  
    int combinationSum4(vector<int>& nums, int target) {
        if(target < 0) {
            return 0;
        }
        if(target == 0) {
            return 1;
        }
        int sum = 0;
        int tmp;
        int newtar;
        for(int i = 0; i < nums.size(); i++) {
            newtar = target - nums[i];
            if(dp.find(newtar) != dp.end()) {
                sum += dp[newtar];
            } else {
                tmp = combinationSum4(nums, newtar);
                sum += tmp;
                dp[newtar] = tmp;
            }
        }
        return sum;
    }
private:  
    unordered_map<int, int> dp;
};

A faster one:

class Solution {  
public:  
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1);
        dp[0] = 1;

        for(int newtar = 1; newtar <= target; newtar++) {
            for(int i = 0; i < nums.size(); i++) {
                if(nums[i] <= newtar) {
                    dp[newtar] += dp[newtar - nums[i]];
                }
            }
        }

        return dp.back();
    }
};