1
class Solution {
2
  private final List<Set<Integer>> allSubsets = new ArrayList<>();
3

4
  public boolean canPartitionKSubsets(int[] nums, int k) {
5
    int sum = Arrays.stream(nums).sum();
6
    if (sum % k != 0) return false;
7
    getAllSubsets(nums.length, sum / k, new HashSet<>(), nums, false);
8
    return allSubsets.size() >= k
9
        && canPartition(allSubsets.size(), k, nums.length, new HashSet<>());
10
  }
11

12
  private boolean canPartition(int n, int k, int size, Set<Integer> current) {
13
    if (k == 0 && current.size() == size) return true;
14
    if (n == 0 || k < 0) return false;
15
    boolean addSet = false;
16
    if (allUnique(current, allSubsets.get(n - 1))) {
17
      current.addAll(allSubsets.get(n - 1));
18
      addSet = canPartition(n - 1, k - 1, size, current);
19
      current.removeAll(allSubsets.get(n - 1));
20
    }
21
    return addSet || canPartition(n - 1, k, size, current);
22
  }
23

24
  private void getAllSubsets(int n, int targetSum, Set<Integer> subsets, int[] nums, boolean lol) {
25
    if (targetSum == 0) {
26
      allSubsets.add(new HashSet<>(subsets));
27
      return;
28
    }
29
    if (n == 0 || targetSum < 0) return;
30
    subsets.add(n - 1);
31
    getAllSubsets(n - 1, targetSum - nums[n - 1], subsets, nums, true);
32
    subsets.remove(n - 1);
33
    getAllSubsets(n - 1, targetSum, subsets, nums, false);
34
  }
35

36
  private boolean allUnique(Set<Integer> set1, Set<Integer> set2) {
37
    for (Integer num : set1) if (set2.contains(num)) return false;
38
    return true;
39
  }
40
}