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