698. Partition to K Equal Sum Su...

This page provides solutions for the leetcode problem 698. Partition to K Equal Sum Subsets.

Problem Explanation

The problem is asking us to check if it is possible to partition an array into $\text{K}$ subarray such that each partition has an equal sum.

Solution

This problem can be solved using backtracking, but since input size is large, we will be use combinations. More such questions can be found here.

Java

import java.util.HashMap;

class Solution {
  private HashMap<Integer, Boolean> memo;
  
  public boolean canPartitionKSubsets(int[] nums, int k) {
    memo = new HashMap<>();
    int totalArraySum = 0;
    for (int num : nums) totalArraySum += num;
    if (totalArraySum % k != 0)  return false;
    return combination(nums, 0, 0, 0, totalArraySum / k, k);
  }

  private boolean combination(int[] nums, int mask, int index, int sum, 
    int requiredSum, int k) {
    if(memo.containsKey(mask)) return memo.get(mask);
    if(k == 0) return true;
    else if(sum > requiredSum) return false;
    else if(sum == requiredSum) {
      boolean ans = combination(nums, mask, 0, 0, requiredSum, k - 1);
      memo.put(mask, ans);
      return ans;
    }

    if(index == nums.length) return false;
    if(((mask >> index) & 1) == 0) {
      mask = (mask | (1 << index));
      if(combination(nums, mask, index + 1, sum + nums[index], requiredSum, k)) {
        memo.put(mask, true);
        return true;
      }
      mask = (mask ^ (1 << index)); 
    }

    if(combination(nums, mask, index + 1, sum, requiredSum, k)) {
      memo.put(mask, true);
      return true;
    }
    memo.put(mask, false);
    return false;
  }
}

info

In this solution we have avoided redundant computations by adding memoization.

Consider if we've chosen the $0$^th and $1$^st elements in set $1$ and the $2$^nd and $3$^rd elements in set $2$, but then found we can't make set $3$ with the remaining items, we remember this situation.

If in different recursive calls, we selected the $0$^th and $3$^rd elements in set $1$, and the $1$^st and $2$^nd elements in set $2$, rather than rechecking if we can create set $3$, we retrieve the previously stored answer (false) from memory.

Complexity

Let's say there are $\text{N}$ elements in an array, and we need to create $\text{K}$ subsets.

Time Complexity

The time complexity is $\text{O}(2^{\text{N}})$ for creating a single subset, as we can either choose or skip each element of an array, and $\text{O}(\text{K})$ for creating $\text{K}$ subsets, so total time complexity will be:

$$\text{O}(\text{K} * 2^{\text{N}})$$

Space Complexity

At any given time, the excution stack will have at most $\text{N}$ elements, so space complexity will be:

$$\text{O}(\text{N})$$