Table of Contents

# Partition Equal Subset Sum – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

Given a **non-empty** array `nums`

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.

**Example 1:**

Input:nums = [1,5,11,5]Output:trueExplanation:The array can be partitioned as [1, 5, 5] and [11].

**Example 2:**

Input:nums = [1,2,3,5]Output:falseExplanation:The array cannot be partitioned into equal sum subsets.

**Constraints:**

`1 <= nums.length <= 200`

`1 <= nums[i] <= 100`

# C++ Partition Equal Subset Sum LeetCode Solution

```
``````
class Solution {
public:
bool canPartition(vector<int>& nums) {
const int MAX_NUM = 100;
const int MAX_ARRAY_SIZE = 200;
bitset<MAX_NUM * MAX_ARRAY_SIZE / 2 + 1> bits(1);
int sum = 0;
for (auto n : nums) {
sum += n;
bits |= bits << n;
}
return !(sum % 2) && bits[sum / 2];
}
};
```

# Java Partition Equal Subset Sum LeetCode Solution

```
``````
public class Solution {
public boolean canPartition(int[] nums) {
// check edge case
if (nums == null || nums.length == 0) {
return true;
}
// preprocess
int volumn = 0;
for (int num : nums) {
volumn += num;
}
if (volumn % 2 != 0) {
return false;
}
volumn /= 2;
// dp def
boolean[] dp = new boolean[volumn + 1];
// dp init
dp[0] = true;
// dp transition
for (int i = 1; i <= nums.length; i++) {
for (int j = volumn; j >= nums[i-1]; j--) {
dp[j] = dp[j] || dp[j - nums[i-1]];
}
}
return dp[volumn];
}
}
```

# Python 3 Partition Equal Subset Sum LeetCode Solution

```
``````
def canPartition(nums):
s, n, memo = sum(nums), len(nums), {0: True}
if s & 1: return False
nums.sort(reverse=True)
def dfs(i, x):
if x not in memo:
memo[x] = False
if x > 0:
for j in range(i, n):
if dfs(j+1, x-nums[j]):
memo[x] = True
break
return memo[x]
return dfs(0, s >> 1)
```

Array-1180

String-562

Hash Table-412

Dynamic Programming-390

Math-368

Sorting-264

Greedy-257

Depth-First Search-256

Database-215

Breadth-First Search-200

Tree-195

Binary Search-191

Matrix-176

Binary Tree-160

Two Pointers-151

Bit Manipulation-140

Stack-133

Heap (Priority Queue)-117

Design-116

Graph-108

Simulation-103

Prefix Sum-96

Backtracking-92

Counting-86

Sliding Window-73

Linked List-69

Union Find-66

Ordered Set-48

Monotonic Stack-47

Recursion-43

Trie-41

Binary Search Tree-40

Divide and Conquer-40

Enumeration-39

Bitmask-37

Queue-33

Memoization-32

Topological Sort-31

Geometry-30

Segment Tree-27

Game Theory-24

Hash Function-24

Binary Indexed Tree-21

Interactive-18

Data Stream-17

String Matching-17

Rolling Hash-17

Shortest Path-16

Number Theory-16

Combinatorics-15

Randomized-12

Monotonic Queue-9

Iterator-9

Merge Sort-9

Concurrency-9

Doubly-Linked List-8

Brainteaser-8

Probability and Statistics-7

Quickselect-7

Bucket Sort-6

Suffix Array-6

Minimum Spanning Tree-5

Counting Sort-5

Shell-4

Line Sweep-4

Reservoir Sampling-4

Eulerian Circuit-3

Radix Sort-3

Strongly Connected Componen-t2

Rejection Sampling-2

Biconnected Component-1