# My 3ms Java DP solution

• Wish to learn better solutions from you guys.

``````public class Solution {
public int combinationSum4(int[] nums, int target) {
Arrays.sort(nums);
int[] res = new int[target + 1];
for (int i = 1; i < res.length; i++) {
for (int num : nums) {
if (num > i)
break;
else if (num == i)
res[i] += 1;
else
res[i] += res[i-num];
}
}
return res[target];
}
}
``````

• @feiyoshang Awesome! Upvoted. Could you share a little bit of your thought process?

• @steve.j.sun At first I tried the recursive version, but got TLE, then this DP solution came to me. The idea comes from https://leetcode.com/problems/climbing-stairs/

• @feiyoshang Exactly, my recursive solution got TLE as well. Thanks for pointing to that problem!

• Why do you need to sort it?

• @haruhiku Because in the loop `for (int num: nums) {}` we have a `break;`. Actually if the `nums` is not sorted, we could `continue` when `num > i`, the code could still pass the tests.

• @feiyoshang
Thanks for sharing.
By any chance I can see your first TLE recursive solution?

I sort of want to know how to find DP solution from normal recursion.

• @reboot329
My recursion solution is here. The key of not getting TLE is to use memory storing the resulting count of each target value discovered.

Thanks a lot!!

• perfect！learn a lot

• good solution, but some cases such as
[100000000,200000000,300000000]
1400000000
will get Memory Limit Exceeded due to you assign the length of "res" array as target+1,
to avoid that we could use Memory optimization search

``````public class Solution {
HashMap<Integer, Integer> hashmap;

public int combinationSum4(int[] nums, int target)
{
int len=nums.length;
Arrays.sort(nums);
hashmap=new HashMap<>(len);
search(nums, target);
return hashmap.get(target);
}

public int search(int[] nums,int target)
{
if(hashmap.containsKey(target))
return hashmap.get(target);

int index=Arrays.binarySearch(nums, target);
boolean exist=index>=0;
if(index<0)
index=-(index+1);

int sum=(exist?1:0);

for(int i=index-1;i>=0;i--)
{
int dis=target-nums[i];
sum+=search(nums, dis);
}

hashmap.put(target, sum);
return sum;
}
}
``````

• @wdlsjdl Thanks for your share! It is indeed a problem when target is a big integer! There exists a lot of waste of time and memory

• Sorting is unnecessary.
I would recommend my 1ms pure DP solution without sorting.

• @feiyoshang smart thought !

• @feiyoshang Nice solution! Little modification in the code. We can reduce many if-else conditions :)

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

``````    for (int i = 1; i < res.length; i++) {
for (int num : nums) {
if (num > i)
break;
res[i] += res[i-num];
}
}
return res[target];
}
``````

}

• Did you pass all test cases?

Input:
[1,2]
10
expected: 89

I run your code and get output 9.

• @yaohaiqiong it is 89

• Can anyone explain some about "res[i] += res[i - num];"? Thx.

• @haruhiku After sort,when you find that num > i which means you can't remove any more to reduce the problem to a smaller one.

• @feiyoshang Your solution is great! One minor improvement I can think of is to use res[0]. Assume empty list is putting zero elements in a list. So there is 1 way to create empty list. This will help remove the check if n is equal to i or not.

``````public int combinationSum4(int[] nums, int target) {
Arrays.sort(nums);
int[] res = new int[target+1];
res[0]=1; // 1 way to create empty combination.
for(int i=0 ;i<=target; i++)
{
for(int n : nums)
{
if(n>i) break;
res[i]+=res[i-n];
}
}
return res[target];
}``````

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