Combination Sum IV

문제

https://leetcode.com/problems/combination-sum-iv/description/

입력

1 <= nums.length <= 200
1 <= nums[i] <= 1000
1 <= target <= 1000

결과

ans: Int = nums를 이용해 target을 만들 수 있는 중복조합의 수

해석

dfs와 memorization을 섞은 문제로 해석 된다.

target을 nums에 있는 수 만큼 내리는 top-down 방식으로 해결

target이 음수로 가면 가능성이 없으므로 0

target이 0이면 1을 리턴 

코드

class Solution {
    func combinationSum4(_ nums: [Int], _ target: Int) -> Int {
        var cache: [Int] = [Int](repeating: -1, count: target+1)
        cache[0] = 0
        return dfs(target, nums, &cache)
    }

    func dfs(_ target: Int, _ nums: [Int],_ cache: inout [Int]) -> Int {
        if target < 0 {
            return 0
        }
        
        if target == 0  {
            return 1 
        }

        if cache[target] != -1 {
            return cache[target]
        }

        var count: Int = 0

        for num in nums {
            count += dfs(target-num, nums, &cache)
        }
        cache[target] = count 
        return count
    }
}