[LeetCode] 494. Target Sum

😎풀이

1. 깊이 우선 탐색
   1-1. 현재 인덱스에서의 합이 이미 기록된 상태라면, 캐싱된 데이터 사용
   1-2. 현재 인덱스의 수를 더하거나 뺀 상황에서의 경우의 수 탐색
   1-3. 두 경우의 수를 조합하여 현재 경우의 수 캐싱 및 반환
2. nums의 첫번째 요소부터 모든 요소를 더하거나 빼서 target을 만드는 경우의 수 반환

function findTargetSumWays(nums: number[], target: number): number {
    const map = new Map<string, number>()
    function dfs(idx: number, sum: number) {
        if(idx === nums.length) return sum === target ? 1 : 0
        const key = idx + ',' + sum
        if(map.has(key)) return map.get(key)
        const num = nums[idx]
        const add = dfs(idx + 1, sum + num)
        const subtract = dfs(idx + 1, sum - num)
        const result = add + subtract
        map.set(key, result)
        return result
    }
    return dfs(0, 0)
};