## Algorithm

Problem Name: 416. 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:

```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`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
bool canPartition(int* nums, int numsSize) {
int t, s, i, k;
bool *dp, ans;

t = 0;
for (i = 0; i  <  numsSize; i ++) {
t += nums[i];
}

if (t & 1) return false;

t >>= 1;

dp = calloc(t + 1, sizeof(bool));
//assert(dp);

dp[0] = true;
for (i = 0; !dp[t] && i  <  numsSize; i ++) {
k = nums[i];
for (s = t; s >= k; s --) {
dp[s] = dp[s - k];
}
}

ans = dp[t];

free(dp);

return ans;
}
``````
Copy The Code &

Input

cmd
nums = [1,5,11,5]

Output

cmd
true

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
bool canPartition(vector<int>& nums) {
// dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]]
int sum = 0;
for(auto x: nums) sum += x;
if(sum % 2) return false;
vector<vector < bool>>dp(nums.size(>, vector < bool>(sum / 2 + 1, false));
dp[0][0] = true;
for(int i = 1; i  <  nums.size(); i++)
for(int j = 0; j  <  sum / 2 + 1; j++)
dp[i][j] = dp[i - 1][j] || ((j >= nums[i]) ? dp[i - 1][j - nums[i]] : 0);
return dp[nums.size() - 1][sum / 2];
}
};
``````
Copy The Code &

Input

cmd
nums = [1,5,11,5]

Output

cmd
true

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 2 == 1) {
return false;
}
sum /= 2;
int n = nums.length;
boolean[] dp = new boolean[sum + 1];
dp[0] = true;
for (int num : nums) {
for (int i = sum; i > 0; i--) {
if (i >= num) {
dp[i] = dp[i] || dp[i - num];
}
}
}
return dp[sum];
}
}
``````
Copy The Code &

Input

cmd
nums = [1,2,3,5]

Output

cmd
false

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const canPartition = function(nums) {
let sum = 0
for(let num of nums) {
sum += num
}

if(sum & 1 === 1) {
return false
}

sum /= 2
let n = nums.length
const dp = Array.from(new Array(n+1), () => [])
for(let i = 0; i < dp.length; i++) {
dp[i] = new Array(sum+1).fill(false)
}
dp[0][0] = true
for(let i = 1; i  <  n + 1; i++) {
dp[i][0] = true
}
for(let j = 1; j  <  sum + 1; j++) {
dp[0][j] = false
}
for(let i = 1; i  <  n + 1; i++) {
for(let j = 1; j  <  sum + 1; j++> {
if(j >= nums[i - 1]) {
dp[i][j] = (dp[i -1][j] || dp[i - 1][j - nums[i - 1]])
}
}
}
return dp[n][sum]
};
``````
Copy The Code &

Input

cmd
nums = [1,2,3,5]

Output

cmd
false

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def canPartition(self, nums):
sm, n = sum(nums), len(nums)
if sm % 2:
return False
sm //= 2
dp = [False] * (sm + 1)
dp[0] = True
for num in nums:
for j in range(num, sm + 1)[::-1]:
dp[j] = dp[j] or dp[j - num]
return dp[-1]
``````
Copy The Code &

Input

cmd
nums = [1,5,11,5]

Output

cmd
true

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
using System;

namespace LeetCode
{
public class _0416_PartitionEqualSubsetSum
{
public bool CanPartition(int[] nums)
{
int sum = 0, max = int.MinValue;
foreach (var num in nums)
{
sum += num;
max = Math.Max(num, max);
}
if (sum % 2 != 0 || max > sum / 2) return false;
return CanPartition(nums, 2, new bool[nums.Length], sum / 2, 0, 0);
}

private bool CanPartition(int[] nums, int k, bool[] visited, int target, int current, int index)
{
if (k == 1) return true;
if (target == current)
return CanPartition(nums, k - 1, visited, target, 0, 0);

for (int i = index; i  <  nums.Length; i++)
{
if (visited[i]) continue;
if (current + nums[i] > target) continue;

visited[i] = true;

if (CanPartition(nums, k, visited, target, current + nums[i], i)) return true;

visited[i] = false;
while (i + 1  <  nums.Length && nums[i] == nums[i + 1])
i++;
}

return false;
}
}
}
``````
Copy The Code &

Input

cmd
nums = [1,5,11,5]

Output

cmd
true