# Partition Equal Subset Sum 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:** ```plaintext Input: nums = [1,5,11,5] Output: true Explanation: The array can be partitioned as [1, 5, 5] and [11]. ``` **Example 2:** ```plaintext 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): ```plaintext 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 `remaining`using 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) ```javascript /** * 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` s`using the first`i `numbers?` 3. **Base cases**: * `dp[0][0] = true` (sum of 0 with 0 items) * `dp[0][s] = false` for `s > 0` 4. **Transition**: ```plaintext 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) ```javascript /** * 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) ```javascript /** * 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.