LeetCode 416 - Partition Equal Subset Sum (Medium)

문제

LeetCode - 416번

풀이 과정

주어진 배열에서 두 그룹으로 나누었을 때 두 그룹의 합이 같은 경우가 존재하는지 찾는 문제입니다.

0-1 knapsack 문제와 비슷하게 특정 인덱스의 숫자를 선택할지 안할지를 따져서 문제를 해결하면 됩니다.
우선 목표 합 target = total / 2 이며 나누어 떨어지지 않는 경우는 해가 존재하지 않으므로 이를 따로 예외처리합니다.
그 다음 dp[i, k] = i 이후 숫자들을 선택해서 합이 k 가 되는 경우가 존재하는지 라고 정의한다면
다음과 같은 점화식을 얻을 수 있습니다.

dp[i, k] = dp[i+1, k-num[i]] or dp[i+1, k]

코드

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function (nums) {
  const acc = nums.reduce((acc, n) => acc + n);
  if (acc % 2) return false;

  const target = acc / 2;
  const memo = new Array(nums.length + 1)
    .fill(0)
    .map((_) => new Array(target + 1).fill(-1));

  function dp(i, k) {
    if (k === 0) return 1;
    else if (i + 1 >= nums.length || k < 0) return 0;

    if (memo[i + 1][k] !== -1) return memo[i + 1][k];

    memo[i + 1][k] = dp(i + 1, k - nums[i]) || dp(i + 1, k);
    return memo[i + 1][k];
  }

  nums.unshift(0);
  const answer = dp(-1, target);
  return answer;
};