Partition to K Equal Sum Subsets Solution in C++

Problem Description

So, you think you can partition a set of numbers into K equal sum subsets? Well, welcome to the club! This problem is like trying to divide a pizza among your friends, but instead of slices, you have numbers, and instead of friends, you have subsets. The catch? Each subset must have the same total sum.

Imagine you have a bag of assorted candies, and you want to share them equally among your friends. But wait! One of your friends is on a diet and can only take a specific amount. Now, you have to figure out if you can still share the candies without anyone feeling left out. Sounds fun, right?

In technical terms, given an array of integers nums and an integer k, the task is to determine if it’s possible to partition nums into k subsets such that the sum of each subset is equal.

Code Solution


class Solution {
 public:
  bool canPartitionKSubsets(vector& nums, int k) {
    const int sum = accumulate(nums.begin(), nums.end(), 0);
    if (sum % k != 0)
      return false;

    const int target = sum / k;  // the target sum of each subset
    if (ranges::any_of(nums, [target](const int num) { return num > target; }))
      return false;

    ranges::sort(nums, greater<>());
    return dfs(nums, 0, k, /*currSum=*/0, target, /*used=*/0);
  }

 private:
  bool dfs(const vector& nums, int s, int remainingGroups, int currSum,
           const 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.size(); ++i) {
      if (used >> i & 1)
        continue;
      if (dfs(nums, i + 1, remainingGroups, currSum + nums[i], subsetTargetSum,
              used | 1 << i))
        return true;
    }

    return false;
  }
};

Approach

The approach taken in this solution is a classic backtracking method. First, we check if the total sum of the array can be evenly divided by k. If not, we can immediately return false. Next, we sort the numbers in descending order to optimize the search. The dfs function is then called to explore all possible combinations of numbers to form subsets that meet the target sum.

The function keeps track of the current sum and the number of remaining groups. If a valid group is found, it resets the current sum and decreases the remaining groups. The process continues until either all groups are formed or all possibilities are exhausted.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(2ⁿ), where n is the number of elements in `nums`. This is due to the nature of the backtracking approach, which explores all subsets.
Space Complexity	O(n), for the recursion stack in the worst case.

Real-World Example

Imagine you’re organizing a charity event and you have a collection of donations (represented by the array nums). You want to distribute these donations equally among k different causes. If you can successfully partition the donations into equal sums, you can ensure that each cause receives the same amount, making it a fair distribution. If not, well, someone might end up with a lot more than others, and we all know how that ends!