Idea is same as the solution posted by @FreeTymeKiyan .

It helps to imagine the overlapping sub problems-

- Consider you come up with a recursive solution which maintains the value needed to reach the target.
- 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. - 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.
- 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 - 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.
- Also naturally as this is a TOP DOWN approach, most time is saved at the TOP levels.

**Couple of minor details**-

- 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> - 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;
}
```