Combination Sum IV

https://leetcode.com/problems/combination-sum-iv/#/description

DFS Solution(Time Limit Exceeded)

public class Solution {
    int res;
    public int combinationSum4(int[] nums, int target) {
        res = 0;
        Arrays.sort(nums);
        dfs(nums, target, 0, 0);

        return res;
    }

    private void dfs(int[] nums, int target, int sum, int start){
        if(target == sum){
            res++;
            return;
        }

        for(int i = 0; i < nums.length; i++){
            if(sum + nums[i] > target){
                break;
            }

            dfs(nums, target, sum + nums[i], 0);
        }
    }
}

Recursion(Time Limit Exceeded)

public class Solution {
    public int combinationSum4(int[] nums, int target) {
        if (target == 0) {
            return 1;
        }
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            if (target >= nums[i]) {
                res += combinationSum4(nums, target - nums[i]);
            }
        }
        return res;
    }
}

DP(bottom-up solution)

//    dp[i] denotes 'valid combinations number for i' until now(when at some position of nums)
//    if nums[j] > i break, 
//    if nums[j] == i, dp[i]++, 
//    if nums[j] < i, dp[i] += dp[i - nums[j]].
//    return dp[target]

public class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        // dp[i] denotes 
        Arrays.sort(nums);
        for(int i = 1; i <= target; i++){
            for(int j = 0; j < nums.length; j++){
                if(nums[j] > i){
                    break;
                }

                if(nums[j] == i){
                    dp[i]++;
                    break;
                }

                dp[i] += dp[i - nums[j]];
            }
        }

        return dp[target];
    }
}

DP(top-down solution)

public class Solution {
    private int[] dp;
    public int combinationSum4(int[] nums, int target) {
        dp = new int[target + 1];
        Arrays.fill(dp, -1);
        dp[0] = 1;
        Arrays.sort(nums);
        return helper(nums, target);
    }

    private int helper(int[] nums, int target){
        if(dp[target] != -1){
            return dp[target];
        }

        dp[target] = 0;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] <= target){
                dp[target] += helper(nums, target - nums[i]);    
            }
        }

        return dp[target];
    }
}

Use HashMap as memorization

public class Solution {
    public int combinationSum4(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        if (nums == null || nums.length ==0 || target < 0 ) return 0;
        map.put(0, 1);
        return helper(nums, target, map);
    }

    private int helper(int[] nums, int target, Map<Integer, Integer> map){
        if(target < 0){
            return 0;
        }
        if (map.containsKey(target)) return map.get(target);
        int count = 0;

        for (int num: nums){
            count += helper(nums, target-num, map);
        }
        map.put(target, count);
        return count;
    }
}

Follow-up(what if we allow negative number):https://discuss.leetcode.com/topic/52290/java-follow-up-using-recursion-and-memorization