Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

Example 1:

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

Below is a comprehensive, step-by-step guide to solve Partition Equal Subset Sum using Dynamic Programming, following the six-part approach we discussed.

---

1) Explain the Problem in Simple Terms

You’re given an array of non-negative integers, e.g. [1, 5, 11, 5]. You want to determine if it can be split into two subsets such that the sum of elements in both subsets is exactly the same.

• For instance, the array [1, 5, 11, 5] can be split into [1, 5, 5] and [11], each summing to 11.

• However, [1, 2, 3, 5] cannot be split into two subsets of equal sum because the total sum is 11, and you can’t split 11 evenly.

Essentially, Partition Equal Subset Sum asks: “Does there exist a subset whose sum is exactly totalSum/2?” If totalSum is odd, the answer is immediately false.

---

2) Draw the Decision (Recursion) Tree

Consider a smaller example: nums = [1, 5, 5]. The total sum is 11, which is odd, so we’d quickly say false. But let’s pretend we check subsets anyway to illustrate a decision tree for a scenario where we attempt to form a target (say 5 or 6).

For a target T = 5 (just as a demonstration):

                canForm(3, 5)  // using first 3 items to form sum=5
               /        \
     Skip last(=5)     Take last(=5)
         /                \
 canForm(2,5)          canForm(2, 0)
        ...                ...

• canForm(i, s) means: “Can we form subset sum s using the first i numbers?”

• You either skip or take the i-th number (if taking it doesn’t exceed the target).

In this problem, we specifically want s = totalSum/2 if totalSum is even.

---

3) Implement the Recursion + Memoization (Top-Down Approach)

Explanation

1. Check if totalSum is even. If it’s odd, return false immediately.

2. Otherwise, define target = totalSum/2.

3. Create a function canPartition(i, remaining) that returns a boolean indicating whether we can form remainingusing the first i elements.

   • If remaining == 0, we found a valid subset → true.

   • If i == 0 and remaining > 0, we don’t have more elements to use → false.

   • We can skip the i-th element, or if nums[i-1] <= remaining, we can also take it.

JavaScript Code (Recursion + Memo)

/**
 * Partition Equal Subset Sum - Recursion + Memoization
 * @param {number[]} nums - array of non-negative integers
 * @return {boolean}
 */
function canPartitionMemo(nums) {
  const totalSum = nums.reduce((a, b) => a + b, 0);

  // If total sum is odd, can't split into two equal subsets
  if (totalSum % 2 !== 0) {
    return false;
  }

  const target = totalSum / 2;
  const n = nums.length;

  // Memo for (i, remaining) -> boolean
  const memo = {};

  function dfs(i, remaining) {
    if (remaining === 0) return true;    // Found a subset
    if (i === 0) return false;          // No items left but still needed sum

    const key = `${i}-${remaining}`;
    if (key in memo) {
      return memo[key];
    }

    // Skip current item
    let result = dfs(i - 1, remaining);

    // Take current item if it fits
    if (nums[i - 1] <= remaining) {
      result = result || dfs(i - 1, remaining - nums[i - 1]);
    }

    memo[key] = result;
    return result;
  }

  return dfs(n, target);
}

// Example usage:
console.log(canPartitionMemo([1,5,11,5])); // true
console.log(canPartitionMemo([1,2,3,5]));  // false

---

4) Implement the Tabulation (Bottom-Up Approach)

Explanation

We can use a Subset Sum DP approach:

1. Let target = totalSum / 2.

2. Create a 2D boolean DP array: dp[i][s] = can we form sum susing the firsti numbers?

3. Base cases:

   • dp[0][0] = true (sum of 0 with 0 items)

   • dp[0][s] = false for s > 0

4. Transition:

    dp[i][s] = dp[i-1][s] 
            OR 
               (dp[i-1][s - nums[i-1]] if nums[i-1] <= s)
   

5. At the end, check dp[n][target].

JavaScript Code (Tabulation)

/**
 * Partition Equal Subset Sum - Bottom-Up DP
 * @param {number[]} nums
 * @return {boolean}
 */
function canPartitionTab(nums) {
  const totalSum = nums.reduce((acc, cur) => acc + cur, 0);
  if (totalSum % 2 !== 0) return false;

  const target = totalSum / 2;
  const n = nums.length;

  // dp[i][s] => can we form sum s using first i elements
  const dp = Array.from({ length: n + 1 }, () => Array(target + 1).fill(false));

  // Base case: dp[0][0] = true
  dp[0][0] = true;

  for (let i = 1; i <= n; i++) {
    const val = nums[i - 1];
    for (let s = 0; s <= target; s++) {
      // Option 1: skip
      dp[i][s] = dp[i - 1][s];

      // Option 2: take the number if it fits
      if (s >= val && dp[i - 1][s - val]) {
        dp[i][s] = true;
      }
    }
  }

  return dp[n][target];
}

// Example usage:
console.log(canPartitionTab([1,5,11,5])); // true
console.log(canPartitionTab([1,2,3,5]));  // false

---

5) Optimize Space Complexity (If Possible)

We notice that each row dp[i][..] depends only on the previous row dp[i-1][..]. Therefore, we can reduce the 2D DP array into a 1D array of size target + 1.

However, we must iterate in descending order of s to avoid using the same element more than once.

JavaScript Code (Space-Optimized Tabulation)

/**
 * Partition Equal Subset Sum - Space-Optimized DP
 * @param {number[]} nums
 * @return {boolean}
 */
function canPartitionTabOptimized(nums) {
  const totalSum = nums.reduce((acc, val) => acc + val, 0);
  if (totalSum % 2 !== 0) return false;

  const target = totalSum / 2;
  const dp = Array(target + 1).fill(false);
  dp[0] = true; // We can always form sum=0 with an empty subset

  for (const num of nums) {
    // Go backward so we don't reuse the same element
    for (let s = target; s >= num; s--) {
      if (dp[s - num]) {
        dp[s] = true;
      }
    }
  }

  return dp[target];
}

// Example usage:
console.log(canPartitionTabOptimized([1,5,11,5])); // true
console.log(canPartitionTabOptimized([1,2,3,5]));  // false

Here, we only use O(target) space.

---

6) Analyze the Time Complexity

Let:

• n = number of elements in nums.

• S = sum of elements in nums.

• Typically, target = S/2.

1. Recursion + Memoization:

   • States: (i, remaining), which can be at most n * target = n * (S/2) = O(nS).

   • Each state is computed once, and each transition is O(1).

   • Time Complexity: O(nS).

   • Space Complexity: O(nS) for the memo, plus up to O(n) recursion depth.

2. Tabulation (2D):

   • We fill a table of size (n+1) x (target+1) → (n+1) x (S/2 + 1).

   • Time Complexity: O(nS).

   • Space Complexity: O(nS).

3. Space-Optimized (1D):

   • Time Complexity is still O(nS), because for each of the n elements, we potentially iterate from target down to num.

   • Space Complexity: O(S) (specifically target + 1).

These complexities are typical for “Subset Sum” and “Partition Equal Subset Sum” type problems.

---

Final Recap

1. Problem: Can the array be split into two subsets of equal sum?

2. Decision Tree: For each element, skip or take it (exponential if naive).

3. Recursion + Memo: Use (i, remaining) states to avoid repeated computations.

4. Tabulation: Build a 2D DP table for subset-sum.

5. Space Optimization: Use a 1D rolling array in descending order of sums.

6. Complexities: O(nS) time, with either O(nS) or O(S) space.

This approach is standard for checking whether a subset with a given sum exists, which directly answers the Partition Equal Subset Sum question.