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

# Partition Equal Subset Sum

Given a **non-empty** array containing **only positive integers**, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

**Note:**

1. Each of the array element will not exceed 100.
2. The array size will not exceed 200.

**Example 1:**

```
Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].
```

**Example 2:**

```
Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.
```

```java
class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int x : nums)
            sum += x;
        if (sum % 2 != 0)
            return false;
        int n = nums.length;
        // using subset sum problem to find a subset which has sum = total sum/2
        boolean dp[][] = new boolean[n + 1][sum / 2 + 1];
        // base case when sum->0 then answer is always true
        for (int i = 0; i <= n; i++)
            dp[i][0] = true;
        // dp[i][k] -> tells us if it is possible to form a subsequence from (0,i) with
        // sum=k
        for (int i = 1; i <= n; i++) {
            for (int k = 1; k <= sum / 2; k++) {
                if (k - nums[i - 1] >= 0)
                    dp[i][k] = dp[i - 1][k] || dp[i - 1][k - nums[i - 1]];
                else
                    dp[i][k] = dp[i - 1][k];
            }
        }
        return dp[n][sum / 2];
    }
}
```