> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/dynamic-programming/partition-equal-subset-sum.md).

# Partition Equal Subset Sum

Problem Statement

<br>

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*.

&#x20;

**Example 1:**

<pre><code><strong>Input: nums = [1,5,11,5]
</strong><strong>Output: true
</strong><strong>Explanation: The array can be partitioned as [1, 5, 5] and [11].
</strong></code></pre>

**Example 2:**

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

&#x20;

**Constraints:**

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

<br>

```
Intution - We have to divide the array target in two parts

Let say if the total sum of array is 20-> 
then we just need to find, If there exists a subset having a sum of target of 10

That is sum/2 

Now if the total sum is odd we cannot divide the sum , hence directly false
```

### Links

{% embed url="<https://leetcode.com/problems/partition-equal-subset-sum/description/>" %}

### Video Link

<https://www.youtube.com/watch?v=7win3dcgo3k&ab_channel=takeUforward>

### Approach 1:

```
Memoization
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    bool subsum(vector<int>& nums, int target, int index, vector<vector<int>> &dp){
        if(target == 0)
            return true;

        if(index == 0)
            return nums[0] == target;

        if(dp[index][target] != -1)
            return dp[index][target]; 

        bool not_take = subsum(nums,target, index-1,dp);

        bool take = false;
        if(target >= nums[index])
            take = subsum(nums, target- nums[index], index-1,dp);

        return dp[index][target] = take or not_take;
    }

    bool canPartition(vector<int>& nums) {
        int target = accumulate(nums.begin(), nums.end(), 0);
        int n = nums.size();
        
        if(target % 2 != 0)
            return false;
        
        vector<vector<int>> dp(n, vector<int>(target/2+1, -1));

        return subsum(nums, target/2, n-1,dp);
    }
};
```

{% endcode %}

### Approach 2:

```
Tabulation
```

{% code title="C++" lineNumbers="true" %}

```cpp
bool canPartition(vector<int>& arr) {
        int sum = accumulate(arr.begin(), arr.end(), 0);
        int n = arr.size();
        
        if(sum % 2 != 0)
            return false;

        int target = sum/2;
        
        vector<vector<bool>> dp(n, vector<bool>(target+1, false));

        for(int i=0; i<n; i++)
            dp[i][0] = true;

        if(arr[0] <= target)
            dp[0][arr[0]] = true;

        for(int index=1; index<n; index++){
            for(int tar=1; tar<=target; tar++){
                bool not_take = dp[index-1][tar];

                bool take = false;
                if(tar>=arr[index])
                    take = dp[index-1][tar-arr[index]];

                dp[index][tar] = take or not_take;
            }
        }

        return dp[n-1][target];
    }
```

{% endcode %}

### Approach 3:

```
Space Optimize
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    bool canPartition(vector<int>& arr) {
        int sum = accumulate(arr.begin(), arr.end(), 0);
        int n = arr.size();
        
        if(sum % 2 != 0)
            return false;

        int target = sum/2;
        
        vector<bool> dp(target+1, false);
        dp[0] = true;
        

        for(int index=1; index<n; index++){
            vector<bool> temp(target+1, false);
            temp[0] = true;

            for(int tar=1; tar<=target; tar++){
                bool not_take = dp[tar];

                bool take = false;
                if(tar>=arr[index])
                    take = dp[tar-arr[index]];

                temp[tar] = take or not_take;
            }
            dp = temp;
        }

        return dp[target];
    }
};
```

{% endcode %}

### Similar Problems