Fastest, easy understanding Java DP Solution


  • 0
    S
    public static int combinationSum41(int[] nums, int target) {
    	if(nums == null || nums.length == 0 || target <= 0) {
    		return 0;
    	}
    	Arrays.sort(nums); //Not required, but can help in exit out of loop early.
    	int[] combinations = new int[target + 1];
    	combinations[0] = 1;
    	int length = nums.length; // so that length is not calculated every time.
    	for (int i = 1; i <= target; i++) {
    		for (int j = 0; j < length; j++) {
    			if(i - nums[j] < 0) {
    				break;
    			}
    			if( i == nums[j]) {
    				combinations[i] += 1;
    			}
    			else if (i - nums[j] >= 0) {
    				combinations[i] += combinations[i - nums[j]];
    			}
    		}
    	}
    	return combinations[target];
    }
    

Log in to reply
 

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