Formatted question description: https://leetcode.ca/all/698.html

698. Partition to K Equal Sum Subsets

Medium

Description

Given an array of integers nums and a positive integer k, find whether it’s possible to divide this array into k non-empty subsets whose sums are all equal.

Example 1:

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

Output: True

Explanation: It’s possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.

Note:

• 1 <= k <= len(nums) <= 16.
• 0 < nums[i] < 10000.

Solution

First calculate the sum of integers in nums and check whether the sum is divisible by k. If the sum is not divisible by k, then it is impossible to divide the array into k non-empty subsets with equal sums, so return false.

Calculate the sum of each subset. Sort the array and check whether the greatest integer in the array is less than or equal to the sum of each subset. If the greatest integer in the array is greater than the sum of each subset, return false.

Use backtrack to determine whether it is possible to divide the array into k non-empty subsets with equal sums. Try each number and add the number to the sum of the current subset. If the sum equals the sum of each subset, then consider the next subset. Continue the step until all subsets are found, and return true. If it is not possible, return false.

Before diving into solution, Let’s first try to understand what Bitmask means. Mask in Bitmask means hiding something. Bitmask is nothing but a binary number that represents something. Let’s take an example.

Consider the set A {1,2,3,4,5}. We can represent any subset of A using a bitmask of length 5, with an assumption that if ith (0<=i<=4) bit is set then it means ith element is present in subset. So the bitmask 01010 represents the subset {2,4}.

Now the benefit of using bitmask. We can set the ith bit, unset the ith bit, check if ith bit is set in just one step each. Let’s say the bitmask, b = 01010.

Set the ith bit: b(1<<i). Let i=0, so,
(1<<i) = 00001
01010 | 00001 = 01011


So now the subset includes the 0th element also, so the subset is {1,2,4}.

Unset the ith bit: b & !(1<<i). Let i=1, so,
(1<<i) = 00010
!(1<<i) = 11101
01010 & 11101 = 01000


Now the subset does not include the 1st element, so the subset is {4}.

Check if ith bit is set: b&(1<<i), doing this operation, if ith bit is set, we get a non zero integer otherwise, we get zero. Let i = 3
(1<<i) = 01000
01010 & 01000 = 01000


Clearly the result is non-zero, so that means 3rd element is present in the subset.

Now coming to our problem, we can represent each number and sum in binary.

We’ll use dynamic programming to find whether the array can be partitioned into k subsets of equal sum. For this, we create two arrays of size = power set of array elements. why?

because, we need to consider all sum subsets.

dp[i] indicates whether array of length i can partitioned into k subsets of equal sum. Using this technique, the last index of this dp array will tell whether the whole array can be partitioned into k subsets of equal sum.

total[i] stores the sum of subset with sum less than equal to target sum (total sum/k why? because we need to split array into k subset).

• Time Complexity : 0(N*2^N)
• Space Complexity: 0(2^N)

Java

class Solution {
public boolean canPartitionKSubsets(int[] nums, int k) {
int sum = 0;
for (int num : nums)
sum += num;
if (sum % k != 0)
return false;
int subsum = sum / k;
Arrays.sort(nums);
int length = nums.length;
if (nums[length - 1] > subsum)
return false;
boolean[] used = new boolean[length];
return backtrack(nums, k, subsum, 0, 0, used);
}

private boolean backtrack(int[] nums, int k, int subsum, int cur, int start, boolean[] used) {
if (k == 0)
return true;
if (cur == subsum)
return backtrack(nums, k - 1, subsum, 0, 0, used);
int length = nums.length;
for (int i = start; i < length; i++) {
if (!used[i] && nums[i] + cur <= subsum) {
used[i] = true;
if (backtrack(nums, k, subsum, nums[i] + cur, i + 1, used))
return true;
used[i] = false;
}
}
return false;
}
}