Python short solution - This is just generalized "Fibonacci"


  • 0
    A
    class Solution(object):
        def combinationSum4(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: int
            """
            # special cases 
            if target <= 0 or len(nums) == 0:
                return 0
            nums = sorted(nums) # O(nlogn)
            from bisect import bisect_right 
            mem = [1] + [0 for _ in range(target)]
            val = 1
            while val <= target:
                pos = bisect_right(nums, val)
                if pos != 0:
                    for i in range(pos):
                        mem[val] += mem[val-nums[i]]
                val += 1
            return mem[target]
    

Log in to reply
 

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