[LeetCode] 494. Target Sum, Medium

1. 문제

• 정수 배열이 주어질 때, 각 요소를 +와 -를 활용해 조합하여 target 수를 만들 수 있는 경우의 수를 반환하라.

2. 해결

function DFS(nums: number[], target: number, sum:number, index: number) {
    
    if(index === nums.length) {
        return sum === target ? 1 : 0;
    }
    
    return DFS(nums,target, sum + nums[index], index +1) + DFS(nums,target, sum -nums[index], index +1);
}

function findTargetSumWays(nums: number[], target: number): number {
    
    return DFS(nums, target, 0, 0);
};

• 첫 번째 요소부터 +와 - 경우를 DFS 탐색해나가면서 마지막 요소에 도달했을 때, target과 같으면 1씩 누적시키면서 반환한다.