문제

• 합이 target인 permutation 생성
• 갯수 return

풀이

• dp 이용

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [0 for _ in range(target+1)] # placeholder 0
        for n in nums:
            if n <= target:
                dp[n] += 1
        
        for i in range(2, target+1):
            for j in range(i):
                if dp[j] and i-j in nums:   
                    dp[i] += dp[j]
        
        return dp[-1]
        

근데 좀 선명하진 않고 때려맞춘 기분.......
미리 만들어둔 dp[j]와 i-j가 nums에 존재한다면 -> 미리 만들어둔 조합 + 숫자하나 해서 새로운 수를 만들 수 있음을 이용했다

결과