Partition to K Equal Sum Subsets Solution in Java

Problem Description

So, you’ve got a bag of candies (or maybe just a bunch of numbers) and you want to share them with your friends. But wait! You want to make sure that everyone gets the same amount. Sounds easy, right? Well, welcome to the world of “Partition to K Equal Sum Subsets,” where you’ll find out that sharing isn’t always caring, especially when it comes to numbers!

Imagine you have a group of friends, and you want to divide your candy stash into K equal piles. If you can’t do it, well, tough luck! You’ll have to eat all the candy yourself (not that we’re complaining). The challenge is to determine if it’s possible to partition the array of integers into K subsets such that each subset has the same sum.

Code Solution


class Solution {
  public boolean canPartitionKSubsets(int[] nums, int k) {
    final int sum = Arrays.stream(nums).sum();
    if (sum % k != 0)
      return false;

    final int target = sum / k; // the target sum of each subset
    if (Arrays.stream(nums).anyMatch(num -> num > target))
      return false;

    return dfs(nums, 0, k, /*currSum=*/0, target, /*used=*/0);
  }

  private boolean dfs(int[] nums, int s, int remainingGroups, int currSum, int subsetTargetSum,
                      int used) {
    if (remainingGroups == 0)
      return true;
    if (currSum > subsetTargetSum)
      return false;
    if (currSum == subsetTargetSum) // Find a valid group, so fresh start.
      return dfs(nums, 0, remainingGroups - 1, 0, subsetTargetSum, used);

    for (int i = s; i < nums.length; ++i) {
      if ((used >> i & 1) == 1)
        continue;
      if (dfs(nums, i + 1, remainingGroups, currSum + nums[i], subsetTargetSum, used | 1 << i))
        return true;
    }

    return false;
  }
}

Approach

The approach used in this solution is a depth-first search (DFS) combined with bit manipulation. The algorithm first checks if the total sum of the array can be evenly divided by K. If not, it returns false. It then uses a recursive function to explore all possible combinations of numbers to form K subsets, each summing to the target value. The bit manipulation helps keep track of which numbers have already been used in the current subset.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(2^N), where N is the number of elements in the array.
Space Complexity	O(N), which is used for the recursion stack.

Real-World Example

Imagine you’re at a party with K friends, and you have a giant pizza. You want to cut it into K equal slices so that everyone gets the same amount. If the pizza is too small or has weird toppings that some friends don’t like, you might end up with a situation where not everyone can get an equal slice. This problem is just like that, but with numbers instead of pizza!