Given a non-empty array of positive integers, determine if the array can be divided into two subsets so that the sum of both subsets is equal.

partition-equal-subsets.js

export function canPartitionArray(nums) {
  // find sum of items
  const total = nums.reduce((acc, num) => acc + num, 0);

  // if there is a remainder, it's not possible to split the array in two subsets with the same sum
  if (total % 2 !== 0) {
    return false;
  }

  // get our half sum, we need to determine if there is a subset that sums up to half sum,
  // because if there is, the rest of the nums will sum up to the same value
  const halfTotal = total / 2;

  // one-dimensional dp array
  // indexes indicate sum
  // so dp[3] answers the question - is there a subset that sums up to 3 with the current state of considered items
  // we fill the array with false values, because initially we don't consider any items from nums
  // if we don't consider any items from nums, there aren't any subsets that can sum up to anything
  const dp = Array(halfTotal + 1).fill(false);
  // except for one, which is an empty subset, that sums up to 0
  // so this answers the question - can we reach sum 0 while considering no items from nums? yes
  // and this will always stay true because even if we consider more items from nums,
  // there will always be an empty subset
  dp[0] = true;

  // outer loop is considering more items
  // so when i is 0, we are only considering first item from nums
  // when i is 1, we are considering item 0 and item 1 (since subproblems for item 0 will be solved at that point)
  for (let i = 0; i < nums.length; ++i) {
    const num = nums[i];
    // iterate dp array backwards
    // solve subproblem - can we reach sum with our currently considered set of items?
    // we can if it has been solved already on the previous iterations of the outer loop,
    // or if we can reach (sum = sum - num) without considering current item
    // ("without" works because we iterate in reverse, and sums that are less still keep their values from the prev iteration of the outer loop)
    for (let sum = halfTotal; sum >= num; --sum) {
      dp[sum] = dp[sum] || dp[sum - num];
    }
  }

  // after the outer loop, dp[halfTotal] contains solution to a subproblem: is there a subset that sums up to halfTotal, if we consider all elements from nums?
  return dp[halfTotal];
}

// tc: O(n * total)
// sc: O(total)