PartitionToEqual { public boolean canPartitionKSubsets(int[] nums, int k) { int sum = IntStream.of(nums).sum(); if (k < 1 || sum % k != 0) { return false; } int avg = sum / k; if (IntStream.of(nums).anyMatch(v -> v > avg)) { return false; } Arrays.sort(nums); reverse(nums); Set<Map<Integer, Integer>> partitions = new HashSet<>(); HashMap<Integer, Integer> o = new HashMap<>(); o.put(avg, k); partitions.add(o); for (int i = 0; i < nums.length; i++) { int v = nums[i]; Set<Map<Integer, Integer>> newPartitions = new HashSet<>(); for (Map<Integer, Integer> partition : partitions) { int[] allPossibles = partition.keySet().stream().filter(t -> t >= v).mapToInt(Integer::valueOf).toArray(); for (int key : allPossibles) { Map<Integer, Integer> next = new HashMap<>(partition); int n = key - v; if (next.get(key) == 1) { next.remove(key); } else { next.put(key, next.get(key) - 1); } next.put(n, next.getOrDefault(n, 0) + 1); newPartitions.add(next); } } if (newPartitions.size() == 0) { return false; } partitions = newPartitions; } return true; }  boolean canPartitionKSubsets(int[] nums, int k);  }
@Test(dataProvider = "partitionsArray") public void test(int[] array, int k, boolean canPartition) { assertEquals(new PartitionToEqual().canPartitionKSubsets(array, k), canPartition); }