# Partition Equal Subset Sum
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/partition-equal-subset-sum)
Canonical: https://scaleengineer.com/dsa/problems/partition-equal-subset-sum
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [EPAM Systems](https://scaleengineer.com/companies/epam-systems), [Flipkart](https://scaleengineer.com/companies/flipkart), [IBM](https://scaleengineer.com/companies/ibm), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Visa](https://scaleengineer.com/companies/visa), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Zoho](https://scaleengineer.com/companies/zoho), [eBay](https://scaleengineer.com/companies/ebay), [Dream11](https://scaleengineer.com/companies/dream11)
---
## Problem
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.

**Constraints:**

* `1 <= nums.length <= 200`
* `1 <= nums[i] <= 100`

# Approaches
## Brute-Force Recursion
This approach explores all possible subsets of the given array `nums` using recursion. For each element, we make two choices: either include it in the current subset or not. We continue this process until we find a subset that sums up to the target value (half of the total sum) or exhaust all possibilities.
**Time:** O(2^n), where `n` is the number of elements in `nums`. For each element, we have two choices, leading to an exponential number of paths to explore. · **Space:** O(n), where `n` is the number of elements in the array. This space is used by the recursion call stack.
**Pros:** Simple to conceptualize and implement.; Follows a clear, divide-and-conquer logic.
**Cons:** Extremely inefficient due to its exponential time complexity.; Leads to a 'Time Limit Exceeded' error on most platforms for non-trivial inputs because it re-computes the same subproblems multiple times.
### Explanation
First, we check a fundamental condition: if the total sum of all numbers in the array is odd, it's impossible to divide them into two subsets of equal sum. In this case, we can immediately return `false`. If the sum is even, we set our `target` to half of the total sum. The problem is now transformed into a search for a subset that adds up to this `target`.

We implement this search using a recursive function. This function explores every possible combination by making two recursive calls at each step for each number: one call that includes the current number in the subset (subtracting its value from the target) and another that excludes it (leaving the target unchanged). If any of these recursive paths eventually reduces the target to zero, it means we've found a valid partition, and we return `true`. If all paths are explored without finding such a subset, we return `false`.

```java
class Solution {
    public boolean canPartition(int[] nums) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        if (totalSum % 2 != 0) {
            return false;
        }

        int targetSum = totalSum / 2;
        return canPartitionRecursive(nums, 0, targetSum);
    }

    private boolean canPartitionRecursive(int[] nums, int index, int target) {
        // Base case: If target is 0, we found a subset.
        if (target == 0) {
            return true;
        }

        // Base case: If we run out of numbers or target becomes negative.
        if (index >= nums.length || target < 0) {
            return false;
        }

        // Recursive step:
        // 1. Include the number at the current index.
        boolean include = canPartitionRecursive(nums, index + 1, target - nums[index]);
        
        // 2. Exclude the number at the current index.
        boolean exclude = canPartitionRecursive(nums, index + 1, target);

        return include || exclude;
    }
}
```
### Algorithm
- Calculate the total sum of all elements in the `nums` array.
- If the total sum is odd, it's impossible to partition it into two equal halves, so return `false`.
- If the total sum is even, calculate the `target` sum, which is `total_sum / 2`.
- Define a recursive helper function, say `canPartitionRecursive(index, target)`, that returns `true` if a subset summing to `target` can be formed using elements from `nums[index]` onwards.
- **Base Cases** for the recursion:
  - If `target` is 0, it means we have found a valid subset, so return `true`.
  - If `target` becomes negative or `index` goes beyond the array bounds, it's an invalid path, so return `false`.
- **Recursive Step**: For the element at `nums[index]`, explore two choices:
  1. **Include `nums[index]`**: Make a recursive call `canPartitionRecursive(index + 1, target - nums[index])`.
  2. **Exclude `nums[index]`**: Make a recursive call `canPartitionRecursive(index + 1, target)`.
- The result for the current state is `true` if either of the two choices returns `true`.
- The initial call to start the process is `canPartitionRecursive(0, target)`.

## Top-Down Dynamic Programming with Memoization
This approach, also known as Top-Down Dynamic Programming, optimizes the brute-force recursion by storing the results of subproblems. The recursive structure is the same, but we use a memoization table (e.g., a 2D array) to cache the result of each state `(index, target)`. When the same subproblem is encountered again, we retrieve the result from the table instead of re-computing it, drastically reducing the number of calculations.
**Time:** O(n * sum). The number of subproblems is `n * sum`, and each subproblem is computed once. · **Space:** O(n * sum), where `n` is the number of elements and `sum` is the target sum. This space is required for the memoization table. The recursion stack also adds O(n) space.
**Pros:** Drastically more efficient than brute-force, with pseudo-polynomial time complexity.; Guarantees that each subproblem is solved only once.; Often retains the intuitive structure of the recursive solution.
**Cons:** The space complexity of O(n * sum) can be large if the target sum is high, potentially leading to memory issues.; While much faster than brute-force, it can be slightly slower than the iterative bottom-up approach due to recursion overhead.
### Explanation
The brute-force approach suffers from solving the same subproblems repeatedly. For instance, finding if a sum of 50 can be made from elements `[10, 20, ...]` might be a subproblem reached through many different paths. Memoization addresses this by caching results.

We define a state by `(index, target)`, representing the subproblem of finding if `target` sum can be achieved using elements from `index` onwards. We use a 2D array, `memo`, where `memo[index][target]` stores the boolean result. We can use an `Integer[][]` array where `null` means not computed, `1` means `true`, and `0` means `false`.

When the recursive function is called for a state `(index, target)`, it first checks the memo table. If a result exists, it's returned immediately. Otherwise, the result is computed recursively, stored in the table, and then returned. This ensures that each unique subproblem is solved only once.

```java
class Solution {
    public boolean canPartition(int[] nums) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        if (totalSum % 2 != 0) {
            return false;
        }

        int targetSum = totalSum / 2;
        // memo[i][j] stores the result for canPartition(i, j)
        // null: not computed, 1: true, 0: false
        Integer[][] memo = new Integer[nums.length][targetSum + 1];
        
        return canPartitionMemo(nums, 0, targetSum, memo);
    }

    private boolean canPartitionMemo(int[] nums, int index, int target, Integer[][] memo) {
        if (target == 0) {
            return true;
        }
        if (index >= nums.length || target < 0) {
            return false;
        }

        if (memo[index][target] != null) {
            return memo[index][target] == 1;
        }

        // 1. Include the number at the current index.
        boolean include = canPartitionMemo(nums, index + 1, target - nums[index], memo);
        
        // 2. Exclude the number at the current index.
        boolean exclude = canPartitionMemo(nums, index + 1, target, memo);

        boolean result = include || exclude;
        memo[index][target] = result ? 1 : 0;
        return result;
    }
}
```
### Algorithm
- Calculate `total_sum` and `target_sum` as in the brute-force approach. Return `false` if `total_sum` is odd.
- Create a memoization table, `memo[n][target_sum + 1]`, where `n` is the number of elements. Initialize it with a value to signify 'not computed' (e.g., `null` or a specific integer like -1).
- Use the same recursive helper function `canPartitionMemo(index, target, memo)`.
- Before any computation, check `memo[index][target]`. If the value has been computed, return it directly.
- If not computed, perform the recursive calls as in the brute-force approach:
  - `result = canPartitionMemo(index + 1, target - nums[index], memo) || canPartitionMemo(index + 1, target, memo)`.
- Store the computed `result` in `memo[index][target]` before returning it.
- The initial call is `canPartitionMemo(0, target_sum, memo)`.

## Space-Optimized Bottom-Up Dynamic Programming
This approach, also known as Bottom-Up Dynamic Programming, is the most optimized solution. It solves the problem iteratively and reduces the space complexity. We use a single 1D array, `dp`, where `dp[j]` indicates whether a sum of `j` can be formed. We iterate through each number in the input array and update this `dp` array to reflect the new sums that become possible by including the current number.
**Time:** O(n * sum). The two nested loops iterate `n` times and `sum` times, respectively. · **Space:** O(sum), where `sum` is the target sum. This is a significant improvement over the O(n * sum) space of the 2D DP/memoization approaches.
**Pros:** Most efficient in terms of space complexity.; Iterative approach avoids recursion overhead and the risk of stack overflow.; Generally the fastest practical solution for this problem's constraints.
**Cons:** The logic, especially the backward iteration, can be less intuitive to grasp compared to the recursive approaches.; The time complexity is still dependent on the target sum, making it pseudo-polynomial.
### Explanation
This method builds the solution from the ground up. We determine all possible subset sums that can be formed and check if our `target_sum` is one of them.

We use a boolean array `dp` of size `target_sum + 1`. `dp[j] = true` means a subset with sum `j` exists. Initially, only `dp[0]` is `true`.

We then process each number `num` from the input array one by one. For each `num`, we want to update our `dp` array. If we can form a sum `j - num`, then by adding `num`, we can now form the sum `j`. So, the new `dp[j]` should be `true` if the old `dp[j]` was `true` OR if `dp[j - num]` was `true`.

To implement this correctly and avoid using the same number multiple times in a single subset sum (which would be the 'unbounded knapsack' problem), we must iterate the inner loop (for sums `j`) backwards. By iterating from `target_sum` down to `num`, when we calculate `dp[j]`, the value `dp[j - num]` we use is from *before* we considered the current `num` in this pass. This correctly models the 0/1 knapsack logic where each item is used at most once.

After iterating through all numbers, `dp[target_sum]` will hold the final answer.

```java
class Solution {
    public boolean canPartition(int[] nums) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        if (totalSum % 2 != 0) {
            return false;
        }

        int targetSum = totalSum / 2;

        boolean[] dp = new boolean[targetSum + 1];
        dp[0] = true;

        for (int num : nums) {
            for (int j = targetSum; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }

        return dp[targetSum];
    }
}
```
### Algorithm
- Calculate `total_sum` and `target_sum`. Return `false` if `total_sum` is odd.
- Create a 1D boolean array `dp` of size `target_sum + 1`.
- Initialize `dp[0] = true`, as a sum of 0 is always possible (with an empty set). All other `dp[j]` are implicitly `false`.
- Iterate through each number `num` in the input `nums` array.
- For each `num`, perform an inner loop that iterates backwards from `j = target_sum` down to `num`.
- Inside the inner loop, update `dp[j]` with the rule: `dp[j] = dp[j] || dp[j - num]`.
- After iterating through all numbers, the answer is the value of `dp[target_sum]`.

# Solutions
### Java

```java
import java.util.Arrays ; public class Partition_Equal_Subset_Sum { public static void main ( String [] args ) { Partition_Equal_Subset_Sum out = new Partition_Equal_Subset_Sum (); Solution s = out . new Solution (); System . out . println ( s . canPartition ( new int []{ 1 , 5 , 11 , 5 })); System . out . println ( s . canPartition ( new int []{ 1 , 2 , 3 , 5 })); } class Solution { public boolean canPartition ( int [] nums ) { if ( nums == null || nums . length == 0 ) { return false ; } // in case overflow, should use long int sum = sum = Arrays . stream ( nums ). sum (); if ( sum % 2 != 0 ) { // two equal subsets, then sum must be 2*x return false ; } int target = sum / 2 ; // dp[i] 表示原数组是否可以取出若干个数字，其和为i boolean [] dp = new boolean [ target + 1 ]; dp [ 0 ] = true ; for ( int i = 0 ; i < nums . length ; i ++) { for ( int v = target ; v >= nums [ i ]; v --) { dp [ v ] = dp [ v ] || dp [ v - nums [ i ]]; } } return dp [ target ]; } } class Solution_Bitset { /* bool canPartition(vector<int>& nums) { bitset<5001> bits(1); int sum = accumulate(nums.begin(), nums.end(), 0); for (int num : nums) bits |= bits << num; return (sum % 2 == 0) && bits[sum >> 1]; } */ } // only when subset has 2 elements class Solution_2sum { public boolean canPartition ( int [] nums ) { if ( nums == null || nums . length == 0 ) { return false ; } // in case overflow long sum = Arrays . stream ( nums ). reduce ( 0 , ( x , y ) -> ( x + y )); if ( sum % 2 == 1 ) { return false ; // two equal subsets, then sum must be 2*x } // then it's 2Sum question to sum/2 Two_Sum twoSum = new Two_Sum (); Two_Sum . Solution twoSumSolution = twoSum . new Solution (); Arrays . sort ( nums ); // possible overflow return twoSumSolution . twoSum ( nums , ( int ) sum / 2 ) == null ; } } } ////// class Solution { public boolean canPartition ( int [] nums ) { int s = 0 ; for ( int v : nums ) { s += v ; } if ( s % 2 != 0 ) { return false ; } int n = s >> 1 ; boolean [] dp = new boolean [ n + 1 ]; dp [ 0 ] = true ; for ( int v : nums ) { for ( int j = n ; j >= v ; -- j ) { dp [ j ] = dp [ j ] || dp [ j - v ]; } } return dp [ n ]; } }
```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {boolean} */ var canPartition =
  function (nums) {
    let s = 0;
    for (let v of nums) {
      s += v;
    }
    if (s % 2 != 0) {
      return false;
    }
    const m = nums.length;
    const n = s >> 1;
    const dp = new Array(n + 1).fill(false);
    dp[0] = true;
    for (let i = 1; i <= m; ++i) {
      for (let j = n; j >= nums[i - 1]; --j) {
        dp[j] = dp[j] || dp[j - nums[i - 1]];
      }
    }
    return dp[n];
  };

```

### Python

```python
class Solution:
    def canPartition(self, nums: List[int]) -> bool: s = sum(nums) if s % 2 != 0: return False n = s >> 1 dp = [False] * (n + 1) dp[0] = True for v in nums: for target in range(n, v - 1, - 1):  # including v itself dp [ target ] = dp [ target ] or dp [ target - v ] return dp [ - 1 ] class Solution : # recursive, but over time limit in OJ def canPartition ( self , nums : List [ int ]) -> bool : total_sum = sum ( nums ) if total_sum % 2 != 0 : return False target_sum = total_sum // 2 memo = {} # ==> or just use @cache for dfs() def dfs ( idx , curr_sum ): if curr_sum == target_sum : return True if curr_sum > target_sum or idx >= len ( nums ): return False if ( idx , curr_sum ) in memo : return memo [( idx , curr_sum )] # Explore two options: include the current number or exclude it include = dfs ( idx + 1 , curr_sum + nums [ idx ]) exclude = dfs ( idx + 1 , curr_sum ) memo [( idx , curr_sum )] = include or exclude return memo [( idx , curr_sum )] return dfs ( 0 , 0 ) ############ class Solution : def canPartition ( self , nums : List [ int ]) -> bool : m , mod = divmod ( sum ( nums ), 2 ) if mod : return False f = [ True ] + [ False ] * m for x in nums : for j in range ( m , x - 1 , - 1 ): f [ j ] = f [ j ] or f [ j - x ] return f [ m ]

```

### CPP

```cpp
// OJ: https://leetcode.com/problems/partition-equal-subset-sum/ // Time: O(2^N) // Space: O(2^N) class Solution { public: bool canPartition ( vector < int >& A ) { int total = accumulate ( begin ( A ), end ( A ), 0 ); if ( total % 2 ) return false ; unordered_set < int > s , next ; for ( int n : A ) { next = s ; for ( int m : s ) next . insert ( m + n ); next . insert ( n ); if ( next . count ( total / 2 )) return true ; swap ( s , next ); } return false ; } };
```