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 <= 2001 <= 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;
}
Input
nums = [1,5,11,5]
Output
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];
}
};
Input
nums = [1,5,11,5]
Output
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];
}
}
Input
nums = [1,2,3,5]
Output
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]
};
Input
nums = [1,2,3,5]
Output
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]
Input
nums = [1,5,11,5]
Output
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;
}
}
}
Input
nums = [1,5,11,5]
Output
true