Partition to K Equal Sum Subsets Leetcode Solution

Difficulty Level Medium
Frequently asked in Adobe Amazon Apple Bloomberg ByteDance Facebook Google LinkedIn Microsoft Pinterest Salesforce
Array Backtracking Bit Manipulation Bitmask Dynamic Programming ZomatoViews 2628

Problem Statement

The Partition to K Equal Sum Subsets LeetCode Solution – “Partition to K Equal Sum Subsets” states that you’re given the integer array nums and an integer k, return true if it is possible to have k non-empty subsets whose sums are all equal.

Example:

Input:  nums = [4,3,2,3,5,2,1], k = 4
Output: true

Explanation:

  • The sum of the input array is 20.
  • Hence, we need to partition the array into 4 non-empty subsets each having sum of 5.
  • One of the possible partition is: [[5], [1,4], [2,3], [2,3]].
Input:  nums = [1,2,3,4], k = 3
Output: false

Explanation:

  • The sum of the input array is 10, which is not divisible by 3.
  • Hence, we cannot have a valid partition.

Approach

Idea:

  1. The main idea to solve this problem is to use Backtracking.
  2. First, we will sort the array in non-increasing order which will ensure that there would be less number of recursion calls(recursion branches) since there would be less change in the subset-sum.
  3. Find the sum and the sum of all the elements of the input array.
    1. If the sum is a multiple of k, then we can have k subsets whose sums are all equal.
    2. Otherwise, return false.
  4. Also, we would perform memoization of the results into a HashMap, which would improve the runtime complexity of the solution since it would avoid the same recursive calls again.
  5. So, we’ll check if the result for the current configuration is already stored in the hashmap, and return the cached result.
  6. For each element that is still not taken:
    1. Include the number into the current subset and set the current bit position as 1.
    2. We’ll make the recursive call for the next element.
      1. If this recursive call returns true, we had found the valid partition, hence return true here.
      2. Else, discard the current element by setting the current bit position as 0, and try the next element.
  7. When the current sum of the subset reaches the demand sum, start working over the next subset by decrementing the value of k.
  8. When k==1, which implies we have found all the subsets and the remaining elements must have the sum equal to the demand sum.
  9. We’ll memorize the result of this configuration(the elements which are taken) using the integer mask.

Code

Partition to K Equal Sum Subsets Leetcode C++ Solution:

class Solution {
public:
    bool recurse(int currsum,int demandsum,int start,int k,int& mask,vector<int>& nums,unordered_map<int,int>& memo){
        if(k==1){
            return true;
        }
        if(currsum>demandsum){
            return false;
        }
        if(memo.count(mask)){
            return memo[mask];
        }
        if(currsum==demandsum and recurse(0,demandsum,0,k-1,mask,nums,memo)){
            return memo[mask] = true;
        }
        for(int i=start;i<nums.size();i++){
            if((1<<i)&mask){
                continue;
            }
            mask |= (1<<i);
            if(recurse(currsum+nums[i],demandsum,i+1,k,mask,nums,memo)){
                return true;
            }
            mask ^= (1<<i);
        }
        return memo[mask] = false;
    }
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = accumulate(nums.begin(),nums.end(),0);
        if(sum%k or nums.size()<k){
            return false;
        }
        int mask = 0;
        unordered_map<int,int> memo;
        sort(nums.rbegin(),nums.rend());
        return recurse(0,sum/k,0,k,mask,nums,memo);
    }
};

Partition to K Equal Sum Subsets Leetcode Java Solution:

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
    int sum = 0;
    for (int n : nums) sum += n;
    if (sum % k != 0) return false;
    if (nums.length < k) return false;
    return canPartition(nums, new boolean[nums.length], 0, k, 0, sum / k);
  }
  private boolean canPartition(int[] nums, boolean[] used, int start, int k, int curSum, int subSum) {
    if (k == 1) return true;
    if (curSum > subSum) return false;
    if (curSum == subSum) return canPartition(nums, used, 0, k - 1, 0, subSum);
    for (int i = start; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true;
      if (canPartition(nums, used, i + 1, k, curSum + nums[i], subSum)) return true;
      used[i] = false;
    }
    return false;
  }
}

Complexity Analysis for Partition to K Equal Sum Subsets Leetcode Solution

Time Complexity

The time complexity of the above code is O(N*2^N)  when we use memoization with backtracking since there will be 2^N unique combinations of building a subset from an array of length N, in every combination the given array will be linearly iterated.

Space Complexity

The space complexity of the above code is O(2^N). There will be 2^N unique combinations of the integer mask  which will be stored in the map, and the recursive stack will require O(N) space.

Translate »