LeetCode 494 - Target Sum (Medium)

문제

LeetCode - 494번

풀이 과정

양의 정수들로 이루어진 배열이 주어질 때 + 와 - 를 적절히 사용해서 특정 합 S 를 만들 수 있는 경우의 수를 찾는 문제입니다.

배열의 길이가 최대 20 이고 + 와 - 두 가지만 존재하기 때문에 최대 2^20 의 경우의 수만 탐색하면 됩니다.
따라서 DFS 를 이용해서 모든 경우의 수를 따져봐도 되지만 DFS 과정에서 중복이 발생할 수 있고
최적 부분 구조를 따르기 때문에 동적 계획법 을 사용해서 문제를 해결했습니다.

dp(x, sum) = 배열의 x 위치부터 선택해서 그 합이 sum을 만족시키는 경우의 수 라고 한다면
다음과 같은 점화식을 세울 수 있습니다.

dp(x, sum) = dp(x+1, sum + x) + dp(x+1, sum - x)

코드

/**
 * @param {number[]} nums
 * @param {number} S
 * @return {number}
 */
var findTargetSumWays = function (nums, S) {
  const cache = new Map();

  function dp(x, sum) {
    if (x === nums.length) return sum === S ? 1 : 0;

    const key = `${x}#${sum}`;
    if (cache.has(key)) return cache.get(key);

    const result = dp(x + 1, sum + nums[x]) + dp(x + 1, sum - nums[x]);
    cache.set(key, result);
    return result;
  }

  const answer = dp(0, 0);
  return answer;
};