Simple Python recursion + memorization

  • 0
        def combinationSum4(self, nums, target):
            :type nums: List[int]
            :type target: int
            :rtype: int
            def recCount(startIdx, nums, target, mem):
                if target == 0:
                    return 1
                if target < 0:
                    return 0
                if (startIdx, target) in mem:
                    return mem[(startIdx, target)]
                mem[(startIdx, target)] = 0
                for i in range(startIdx, startIdx + len(nums)):
                    # circle the nums array starting from the given startIdx
                    # not exclude the current num pointed by the startIdx for the next recursion
                    mem[(startIdx, target)] += recCount(i % len(nums), nums, target - nums[i % len(nums)], mem)
                return mem[(startIdx, target)]
            # memorize each pair of starting Idx and target
            mem = {}
            return recCount(0, nums, target, mem)

Log in to reply

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