Скачать или смотреть 59 - Partition Equal Subset Sum - Final DP solution in Java

‪@backstreetbrogrammer‬

Pseudo code:

int sum = SUM(nums[]);

// if sum is odd, return false
if (sum % 2 == 1) return false;

Set dp;
dp.add(0);

int target = sum / 2;
for (int num : nums) {
Set tmp;
for (int dpNum : dp) {
int currSum = dpNum + num;
if (currSum == target) {
return true;
}
tmp.add(currSum);
tmp.add(dpNum);
}
dp.addAll(tmp);
}

return dp.contains(target);

Time complexity: O(n^2)
Space complexity: O(sum(nums[])^2) ~ O(n^2)

Github: https://github.com/backstreetbrogramm...

Leetcode: https://leetcode.com/problems/partiti...

Dynamic Programming Playlist:    • Dynamic Programming  
Dynamic Programming Github: https://github.com/backstreetbrogramm...

Java Serialization Playlist:    • Java Serialization  
Java Serialization Github: https://github.com/backstreetbrogramm...

#java #javadevelopers #javaprogramming #algorithms #datastructuresandalgorithms #dynamicprogramming #onemonthofdynamicprogramming