Combination Sum IV

Problem: Combination Sum IV

Since we can have duplicates, every time we do backtracking we don't need to remove the element we add to the combination. Also we can use memoization to reduce running time.

Code in Python:

class Solution(object):
    def combinationSum4(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        nums.sort()
        self.history = {}
        return self.combinationSum(nums, target)

    def combinationSum(self, nums, target):
        if not nums: return 0
        if target in self.history: return self.history[target]

        res = 0
        for i, num in enumerate(nums):
            if num > target: break
            if num == target: res += 1
            else: res += self.combinationSum(nums, target-num)
        self.history[target] = res
        return res