Number factors

Given a number ‘n’, implement a method to count how many possible ways there are to express ‘n’ as the sum of 1, 3, or 4. Sample Example 1: n : 4 Number of ways = 4 Explanation: Following are the four ways we can express ‘n’ : {1,1,1,1 }, {1,3}, {3,1}, {4}

Input: nums = [1,2,3], target = 4 Output: 7 Explanation: The possible combination ways are: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)

Note that different sequences are counted as different combinations.

from typing import List
class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        pass

Recursion

from typing import List
class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        n = len(nums)
        def combinationSum(nums, target):
            if target == 0:
                return 1
            w = 0
            for i in range(len(nums)):
                if nums[i] <= target:
                    w += combinationSum(nums, target-nums[i])
            return w
        return combinationSum(nums, target)

x = Solution()
x.combinationSum4([1,2,3], 4)

7

Recursion with Memoization

from typing import List
class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        n = len(nums)
        mem = {}
        def combinationSum(nums, target):
            if target in mem:
                return mem[target]
            if target == 0:
                return 1
            w = 0
            for i in range(len(nums)):
                if nums[i] <= target:
                    w += combinationSum(nums, target-nums[i])
            mem[target] = w
            return mem[target]
        return combinationSum(nums, target)

x = Solution()
x.combinationSum4([1,2,3], 1)

1

Dp table

from typing import List
class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        if target < 1: return 0
        dp = [0 for _ in range(target+1)]
        dp[0] = 1

        for i in range(1,len(dp)):
            for n in nums:
                if(i-n > -1):
                    dp[i] += dp[i-n]
        return dp[-1]
        

x = Solution()
x.combinationSum4([1,2,3], 4)

7