377.-combination-sum-iv.md

377. Combination Sum IV

• Medium

• Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

  The test cases are generated so that the answer can fit in a 32-bit integer.

Analysis

The problem is the same as changing coins and that kind of problems. Therefore a bottom up recursion would solve the problem.

class Solution(object):
    def combinationSum4(self, nums, target):
        nums, combs = sorted(nums), [1] + [0] * (target)
        for i in range(target + 1):
            for num in nums:
                if num  > i: break
                if num == i: combs[i] += 1
                if num  < i: combs[i] += combs[i - num]
        return combs[target]