Repository: TheAlgorithms/Java
Pull request #4182 (2023-05-08 08:28:31)

Partition Problem using Dynamic Programming
<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.


siriak: Sure
asifjoardar: @siriak can you please review it again?

Patch:
diff --git a/src/main/java/com/thealgorithms/dynamicprogramming/PartitionProblem.java b/src/main/java/com/thealgorithms/dynamicprogramming/PartitionProblem.java
new file mode 100644
index 00000000..1fbbaf46
--- /dev/null
+++ b/src/main/java/com/thealgorithms/dynamicprogramming/PartitionProblem.java
@@ -0,0 +1,40 @@
+/**
+ * @author Md Asif Joardar
+ *
+ * Description: The partition problem is a classic problem in computer science
+ * that asks whether a given set can be partitioned into two subsets such that
+ * the sum of elements in each subset is the same.
+ *
+ * Example:
+ * Consider nums = {1, 2, 3}
+ * We can split the array "nums" into two partitions, where each having a sum of 3.
+ * nums1 = {1, 2}
+ * nums2 = {3}
+ *
+ * The time complexity of the solution is O(n × sum) and requires O(n × sum) space
+ */
+
+package com.thealgorithms.dynamicprogramming;
+
+import java.util.Arrays;
+
+public class PartitionProblem {
+
+    /**
+     * Test if a set of integers can be partitioned into two subsets such that the sum of elements
+     * in each subset is the same.
+     *
+     * @param nums the array contains integers.
+     * @return {@code true} if two subset exists, otherwise {@code false}.
+     */
+    public static boolean partition(int[] nums)
+    {
+        // calculate the sum of all the elements in the array
+        int sum = Arrays.stream(nums).sum();
+
+        // it will return true if the sum is even and the array can be divided into two subarrays/subset with equal sum.
+        // and here i reuse the SubsetSum class from dynamic programming section to check if there is exists a
+        // subsetsum into nums[] array same as the given sum
+        return (sum & 1) == 0 && SubsetSum.subsetSum(nums, sum/2);
+    }
+}
diff --git a/src/main/java/com/thealgorithms/dynamicprogramming/SubsetSum.java b/src/main/java/com/thealgorithms/dynamicprogramming/SubsetSum.java
index 89544266..07cb448a 100644
--- a/src/main/java/com/thealgorithms/dynamicprogramming/SubsetSum.java
+++ b/src/main/java/com/thealgorithms/dynamicprogramming/SubsetSum.java
@@ -22,7 +22,7 @@ public class SubsetSum {
      * @param sum target sum of subset.
      * @return {@code true} if subset exists, otherwise {@code false}.
      */
-    private static boolean subsetSum(int[] arr, int sum) {
+    public static boolean subsetSum(int[] arr, int sum) {
         int n = arr.length;
         boolean[][] isSum = new boolean[n + 2][sum + 1];
 


Test patch:
diff --git a/src/test/java/com/thealgorithms/dynamicprogramming/PartitionProblemTest.java b/src/test/java/com/thealgorithms/dynamicprogramming/PartitionProblemTest.java
new file mode 100644
index 00000000..ad0aac26
--- /dev/null
+++ b/src/test/java/com/thealgorithms/dynamicprogramming/PartitionProblemTest.java
@@ -0,0 +1,24 @@
+package com.thealgorithms.dynamicprogramming;
+
+import org.junit.jupiter.api.Test;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+class PartitionProblemTest {
+    @Test
+    public void testIfSumOfTheArrayIsOdd(){
+        assertFalse(PartitionProblem.partition(new int[]{1, 2, 2}));
+    }
+    @Test
+    public void testIfSizeOfTheArrayIsOne(){
+        assertFalse(PartitionProblem.partition(new int[]{2}));
+    }
+    @Test
+    public void testIfSumOfTheArrayIsEven1(){
+        assertTrue(PartitionProblem.partition(new int[]{1, 2, 3, 6}));
+    }
+    @Test
+    public void testIfSumOfTheArrayIsEven2(){
+        assertFalse(PartitionProblem.partition(new int[]{1, 2, 3, 8}));
+    }
+}
\ No newline at end of file