Python DFS with tricky parts (memoization and sort) to deal with TLE


  • 0
    S
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        s = sum(nums)
        if s%2 != 0:
            return False
        nums.sort()
        d = {}
        def dfs(target, curr_sum, curr_nums):
            if curr_sum in d:
                return d[curr_sum]
            if curr_sum == target:
                return True
            if curr_sum > target:
                return False
            for i in xrange(len(curr_nums)):
                if curr_sum+curr_nums[i]>target:
                    break
                if dfs(target, curr_sum+curr_nums[i], curr_nums[i+1:]):
                    d[curr_sum] = True
                    return True
            d[curr_sum] = False
            return False
        return dfs(s/2, 0, nums)

Log in to reply
 

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