My 2ms java dp solution


  • 0
    X
    public int combinationSum4(int[] nums, int target) {
        Arrays.sort(nums);
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for(int i = 1; i <= target; i++)
            dp[i] = -1;
        return dpcomb(dp, nums, target);
    }
    private int dpcomb(int[] dp, int[] nums, int target){
        if(target == 0) return 1;
        if(target < 0) return 0;
        dp[target] = 0;
        for(int n : nums){
            if(target >= n){
                if(dp[target - n] < 0) 
                    dp[target] += dpcomb(dp, nums, target - n);
                else
                    dp[target] += dp[target - n];
            }else{
                break;
            }
        }
        return dp[target];
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.