377. Combination Sum IV

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        memo = [None] *(target+1)
        nums.sort()
        def btr(target,nums):
            if target == 0:
                return 1

            if memo[target] != None:
                return memo[target] 
            memo[target] = 0 
            for num in nums:
                if target - num >= 0:
                    memo[target] +=  btr(target-num,nums)
                # else:
                #     return None
            return memo[target]
        btr(target,nums)
        return memo[target] 

 # time O(T*N+ NlgN) space O(T)
class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [0] * (target+1)
        nums.sort() # optimize
        # dp[i]: target == i there is dp[i] ways of combinations 
        # [1, 2, 3]   dp =  [0,1,1,1,0] 
        """
        target 2:
        dp   [1, 0, 0]
        dp:1 [1, 1, 0]
        dp:2 [1, 1, 2]
        dp:3 [1, 1, 2, 4]
             
        1 2 ; 2,1; 1 1 1 , 3
        """
        dp[0] = 1
        for i in range(target+1):
            for num in nums:
                if i - num >= 0:
                    dp[i] += dp[i-num]
                else:  # optimize
                    break  # optimize
           # print(dp)
        return dp[target]