# Python Notebook Solution (beat over 99.3%)

• ``````def combinationSum4(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
nums.sort()
solution = {}
def findSum4(Sum):

result = solution.get(Sum, -1)
if(result >= 0):
return result
result = 0
for i in nums:
if(i < Sum):
result += findSum4(Sum - i)
elif(i == Sum):
result += 1
break
else:
break
solution[Sum] = result
return result
if((not nums) or target <= 0):
return 0
return findSum4(target)
``````

recursive solution suffered TLE
DP solution must calculate a lot of undesired subproblems
In this case, sum for a certain subproblem can serve as the key for the recursive function to search for an available solution in the dictionary(notebook). Since the key is an integer, the search of a hash table is rather low. And notebook solution does not have to calculate undesired subproblems.
So recursive and DP are not the best solution for this problem.

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