add a solution for 698

fishercoder1534 · fishercoder1534 · commit f0bfc2f90771 · 2021-09-30T15:41:15.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_698.java b/src/main/java/com/fishercoder/solutions/_698.java
@@ -1,5 +1,7 @@
 package com.fishercoder.solutions;
 
+import java.util.Arrays;
+
 public class _698 {
 
     public static class Solution1 {
@@ -38,4 +40,56 @@ private boolean canPartition(int[] nums, boolean[] visited, int startIndex, int
         }
     }
 
+    public static class Solution2 {
+        /**
+         * I'm glad that I figured out below solution completely on my own on 9/30/2021.
+         * Backtracking is so beautiful!
+         * <p>
+         * Although not super concise, and I've added a sorting step, it's completely original.
+         */
+        public boolean canPartitionKSubsets(int[] nums, int k) {
+            Arrays.sort(nums);
+            long sum = 0l;
+            for (int num : nums) {
+                sum += num;
+            }
+            int ave = (int) sum / k;
+            if (sum % k != 0) {
+                return false;
+            }
+            boolean[] used = new boolean[nums.length];
+            int found = 0;
+            for (int i = nums.length - 1; i >= 0; i--) {
+                if (!used[i]) {
+                    used[i] = true;
+                    found += recursive(nums, used, ave, nums[i], i);
+                }
+            }
+            return k == found;
+        }
+
+        private int recursive(int[] nums, boolean[] used, int targetSum, int currSum, int currIndex) {
+            if (currSum == targetSum) {
+                return 1;
+            } else if (currSum > targetSum) {
+                used[currIndex] = false;
+                return 0;
+            } else {
+                if (currIndex > 0) {
+                    for (int i = currIndex; i > 0; i--) {
+                        if (!used[i - 1]) {
+                            used[i - 1] = true;
+                            int found = recursive(nums, used, targetSum, currSum + nums[i - 1], i - 1);
+                            if (found == 1) {
+                                return found;
+                            }
+                            used[i - 1] = false;//this is the backtracking step: reset this number to be available if not found
+                        }
+                    }
+                }
+                return 0;
+            }
+        }
+    }
+
 }
diff --git a/src/test/java/com/fishercoder/_698Test.java b/src/test/java/com/fishercoder/_698Test.java
@@ -8,12 +8,14 @@
 
 public class _698Test {
     private static _698.Solution1 solution1;
+    private static _698.Solution2 solution2;
     private static int[] nums;
     private static int k;
 
     @BeforeClass
     public static void setup() {
         solution1 = new _698.Solution1();
+        solution2 = new _698.Solution2();
     }
 
     @Test
@@ -25,8 +27,59 @@ public void test1() {
 
     @Test
     public void test2() {
-        nums = new int[]{-1,1,0,0};
+        nums = new int[]{-1, 1, 0, 0};
         k = 4;
         assertEquals(false, solution1.canPartitionKSubsets(nums, k));
     }
+
+    @Test
+    public void test3() {
+        nums = new int[]{4, 3, 2, 3, 5, 2, 1};
+        k = 4;
+        assertEquals(true, solution2.canPartitionKSubsets(nums, k));
+    }
+
+    @Test
+    public void test4() {
+        nums = new int[]{-1, 1, 0, 0};
+        k = 4;
+        assertEquals(false, solution2.canPartitionKSubsets(nums, k));
+    }
+
+    @Test
+    public void test5() {
+        nums = new int[]{2, 2, 2, 2, 3, 4, 5};
+        k = 4;
+        assertEquals(false, solution2.canPartitionKSubsets(nums, k));
+    }
+
+    @Test
+    public void test6() {
+        nums = new int[]{1, 2, 3, 4};
+        k = 3;
+        assertEquals(false, solution2.canPartitionKSubsets(nums, k));
+    }
+
+    @Test
+    public void test7() {
+        nums = new int[]{1, 1, 1, 1, 2, 2, 2, 2};
+        k = 3;
+        assertEquals(true, solution2.canPartitionKSubsets(nums, k));
+    }
+
+    @Test
+    public void test8() {
+        /**This test case clearly shows how backtracking plays out beautifully!*/
+        nums = new int[]{3522, 181, 521, 515, 304, 123, 2512, 312, 922, 407, 146, 1932, 4037, 2646, 3871, 269};
+        k = 5;
+        assertEquals(true, solution2.canPartitionKSubsets(nums, k));
+    }
+
+    @Test
+    public void test9() {
+        nums = new int[]{1, 2, 3, 5};
+        k = 2;
+        assertEquals(false, solution2.canPartitionKSubsets(nums, k));
+    }
+
 }
