# Partition Equal Subset Sum

## Problem#

We are given a non-empty array of positive integers `nums`. Our task is to check whether this array can be divided into two subsets such that the sum of both subsets are equal.

For example,

```Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and .
```
```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`

## Solution#

### Brute Force#

``````public bool CanPartition(int[] nums)
{
int sum = nums.Sum();
if (sum % 2 == 1)
return false;

int subSetSum = sum / 2;
return CanPartition(nums.Length - 1, subSetSum);

bool CanPartition(int n, int subSetSum)
{
if (subSetSum == 0)
return true;
if (n == 0 || subSetSum < 0)
return false;
return CanPartition(n - 1, subSetSum - nums[n - 1]) || CanPartition(n - 1, subSetSum);
}
}
``````

#### Complexity Analysis#

• Time Complexity: At each step we generate two subtree and the height of the tree is `n`. The total number of generated nodes is 2n. Since, we traverse all the nodes, then the complexity will be O(2n).
• Space Complexity: The complexity will be the same with O(recursion depth), thus it will be O(n).

### Top-down Dynamic Programming#

``````public bool CanPartition(int[] nums)
{
int sum = nums.Sum();
if (sum % 2 == 1)
return false;

int subSetSum = sum / 2;
Dictionary<(int, int), bool> memo = new Dictionary<(int, int), bool>();
return CanPartition(nums.Length - 1, subSetSum);

bool CanPartition(int n, int subSetSum)
{
if (subSetSum == 0)
return true;
if (n == 0 || subSetSum < 0)
return false;

if (memo.TryGetValue((n, subSetSum), out var value))
return value;

bool result = CanPartition(n - 1, subSetSum - nums[n - 1]) || CanPartition(n - 1, subSetSum);

return result;
}
}
``````

#### Complexity Analysis#

Suppose `N` is the length of `nums` and `M` equals the `subSetSum`.

• Time Complexity: This problem doesn’t guarantee to have overlapping subproblem unlike typical dynamic programming problem. Therefore, in the worst case the time complexity is O(N x M).
• Space Complexity: The memo will contain N x M entries and the recursion stack will allocate spaces as many as the depth of recursive call (tree), thus the complexity will be O(N x M) since N x M is the dominant part.

### Bottom-up Dynamic Programming#

``````public bool CanPartition(int[] nums)
{
int sum = nums.Sum();
if (sum % 2 == 1)
return false;

int subSetSum = sum / 2;
int n = nums.Length;
bool[,] dp = new bool[n + 1, subSetSum + 1];
dp[0, 0] = true;
for (int i = 1; i <= n; i++)
{
int curr = nums[i - 1];
for (int j = 0; j <= subSetSum; j++)
{
if (j < curr)
dp[i, j] = dp[i - 1, j];
else
dp[i, j] = dp[i - 1, j] || (dp[i - 1, j - curr]);
}
}
return dp[n, subSetSum];
}
``````

#### Complexity Analysis#

Suppose `N` is the length of `nums` and `M` equals the `subSetSum`.

• Time Complexity: Since we have nested loop where the outer loop has length `N` and the inner loop has length `M`, then the time complexity is O(N x M).
• Space Complexity: Since the `dp` array will allocate around N x M spaces, then the complexity will be O(N x M).