Skip to main content

698. Partition to K Equal Sum Subsets

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 K\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.

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 00th and 11st elements in set 11 and the 22nd and 33rd elements in set 22, but then found we can't make set 33 with the remaining items, we remember this situation.

If in different recursive calls, we selected the 00th and 33rd elements in set 11, and the 11st and 22nd elements in set 22, rather than rechecking if we can create set 33, we retrieve the previously stored answer (false) from memory.

Complexity

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

Time Complexity

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

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

Space Complexity

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

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