# Sharing my 1ms Java solution

• Idea is same as the solution posted by @FreeTymeKiyan .

It helps to imagine the overlapping sub problems-

1. Consider you come up with a recursive solution which maintains the value needed to reach the target.
2. Run this on the input [1,2,3] and target = 4. For the sake of understanding imagine you also maintain a list of integers that contribute to the current sum.
When we reach <1,1,1,1> we get our 1st result.
3. It's important to note that each element comes from 1 recursive call. When our last recursive call finishes, we have found the number of ways to get to a sum of 1. Similarly when the 2nd last call finishes, we know the number of ways to get to a sum of 2.
4. These values will be used for future states like
<1,2> will use no of ways to get to a sum of 1
<2> will use no of ways to get to a sum of 2
5. This can be maintained by a 1-d array dp where dp[x] denotes the number of ways to get to a sum of x.
6. Also naturally as this is a TOP DOWN approach, most time is saved at the TOP levels.

Couple of minor details-

1. I always sort the array to make sure I do not make any wasteful calls-
If my list is <1,1,1,1> and target is 4. Then I do not go to state <1,1,1,2>
2. The above condition also eliminates the base case where the current sum is greater than the target.

Here is my code-

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

}

private int helper(int[] nums, int needed, int[] dp){
if(needed == 0)
return 1;
}

if(dp[needed] != -1)
return dp[needed];

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

dp[needed] = combinations;
return combinations;
}
``````

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