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

698. Partition to K Equal Sum Subsets

Level

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.

Using DP with Bit Masking

Ref: https://leetcode.com/problems/partition-to-k-equal-sum-subsets/discuss/335668/DP-with-Bit-Masking-Solution-%3A-Best-for-Interviews

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)
public class Partition_to_K_Equal_Sum_Subsets {


    class Solution {
        public boolean canPartitionKSubsets(int[] nums, int k) {
            if (nums == null || nums.length == 0 || k <= 0) {
                return false;
            }

            int sum = Arrays.stream(nums).sum();
            if (sum % k != 0) {
                return false;
            }

            Arrays.sort(nums);

            int target = sum / k;
            boolean[] isVisited = new boolean[nums.length];

            return dfs(0, 0, k, isVisited, target, nums);
        }

        private boolean dfs(int startIndex, int currentSum, int k, boolean[] isVisited, int target, int[] nums) {

            if (k == 1) return true;
            if (currentSum > target) return false;
            if (currentSum == target) {
                return dfs(0, 0, k - 1, isVisited, target, nums);
            }

            for (int i = startIndex; i < nums.length; i++) {
                if (isVisited[i]) continue;
                isVisited[i] = true;
                if (dfs(i + 1, currentSum + nums[i], k, isVisited, target, nums)) {
                    return true;
                }
                isVisited[i] = false;
            }

            return false;
        }
    }

    // ref: https://leetcode.com/problems/partition-to-k-equal-sum-subsets/solution/
    // @todo: investigate more
    class Solution_dp_Bit_Masking {
        public boolean canPartitionKSubsets(int[] nums, int k) {
            int N = nums.length;
            Arrays.sort(nums);
            int sum = Arrays.stream(nums).sum();
            int target = sum / k;
            if (sum % k > 0 || nums[N - 1] > target) return false;

            boolean[] dp = new boolean[1 << N];
            dp[0] = true;

            int[] total = new int[1 << N];

            for (int state = 0; state < (1 << N); state++) {
                if (!dp[state]) continue;
                for (int i = 0; i < N; i++) {
                    int future = state | (1 << i);
                    if (state != future && !dp[future]) {
                        if (nums[i] <= target - (total[state] % target)) {
                            dp[future] = true;
                            total[future] = total[state] + nums[i];
                        } else {
                            break;
                        }
                    }
                }
            }
            return dp[(1 << N) - 1];
        }
    }


    // ref: https://leetcode.com/problems/partition-to-k-equal-sum-subsets/solution/
    // @todo: investigate more
    class Solution222 {

        public boolean canPartitionKSubsets(int[] nums, int k) {

            if (nums == null || nums.length == 0 || k <= 0) {
                return false;
            }

            int sum = Arrays.stream(nums).sum();
            if (sum % k > 0) { // divident is not int, not possible to achieve
                return false;
            }
            int target = sum / k;

            Arrays.sort(nums);
            int row = nums.length - 1;

            if (nums[row] > target) return false; // optimize, early stop

            while (row >= 0 && nums[row] == target) {
                row--;
                k--;
            }

            return dfs(new int[k], row, nums, target);
        }

        public boolean dfs(int[] groups, int row, int[] nums, int target) {
            if (row < 0) {
                return true;
            }

            int v = nums[row--];
            for (int i = 0; i < groups.length; i++) {

                if (groups[i] + v <= target) { // try to put every element to each of k groups, for an exhuast search
                    groups[i] += v;
                    if (dfs(groups, row, nums, target)) return true;
                    groups[i] -= v;
                }

                if (groups[i] == 0) {
                    break; // all the 0 values of each group occur at the end of the array groups
                }
            }

            return false;
        }
    }

}

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;
    }
}

All Problems

All Solutions