Python Notebook Solution (beat over 99.3%)


  • 0
    J
    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.


Log in to reply
 

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