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) {
        // Memoization
        memo = new HashMap<>();

        // Calculate sum of all elements of an array
        int totalArraySum = 0;
        for (int num : nums) {
            totalArraySum += num;
        }

        // Check if an array can be partitioned into k subsets
        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);

        // K subsets are ready
        if (k == 0) {
            return true;
        } 
        // Current subset sum is greater than required sum
        else if (sum > requiredSum) {
          return false;
        } 
        // Current subset sum is equal to required sum
        else if (sum == requiredSum) {
            // Check if we can create next k - 1 subsets  
            boolean ans = combination(nums, mask, 0, 0, requiredSum, k - 1);
            memo.put(mask, ans);
            return ans;
        }

        if (index == nums.length) return false;

        // Check if current element is visited
        if (((mask >> index) & 1) == 0) {
            // Mark current element as visited 
            mask = (mask | (1 << index));

            // Choose current element 
            if (combination(nums, mask, index + 1, sum + nums[index], 
              requiredSum, k)) {
                memo.put(mask, true);
                return true;
            }

            // Unmark current element as visited
            mask = (mask ^ (1 << index)); 
        }

        // Skip current element 
        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})$$