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 : O(N*2^N)
Space Complexity: O(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;
        }
    }

}

//////

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

//////

class Solution {
    private int[] nums;
    private int[] cur;
    private int s;

    public boolean canPartitionKSubsets(int[] nums, int k) {
        for (int v : nums) {
            s += v;
        }
        if (s % k != 0) {
            return false;
        }
        s /= k;
        cur = new int[k];
        Arrays.sort(nums);
        this.nums = nums;
        return dfs(nums.length - 1);
    }

    private boolean dfs(int i) {
        if (i < 0) {
            return true;
        }
        for (int j = 0; j < cur.length; ++j) {
            if (j > 0 && cur[j] == cur[j - 1]) {
                continue;
            }
            cur[j] += nums[i];
            if (cur[j] <= s && dfs(i - 1)) {
                return true;
            }
            cur[j] -= nums[i];
        }
        return false;
    }
}

// OJ: https://leetcode.com/problems/partition-to-k-equal-sum-subsets/
// Time: O(K^N)
// Space: O(N * SUM(A) / K)
class Solution {
public:
    bool canPartitionKSubsets(vector<int>& A, int k) {
        int sum = accumulate(begin(A), end(A), 0);
        if (sum % k) return false;
        sum /= k;
        vector<int> v(k);
        sort(begin(A), end(A), greater<>()); // Try the rocks earlier than sands
        function<bool(int)> dfs = [&](int i) {
            if (i == A.size()) return true;
            for (int j = 0; j < k; ++j) {
                if (v[j] + A[i] > sum) continue;
                v[j] += A[i];
                if (dfs(i + 1)) return true;
                v[j] -= A[i];
                if (v[j] == 0) break; // don't try empty buckets multiple times.
            }
            return false;
        };
        return dfs(0);
    }
};

'''
eg: [1,2,3,4], k=2

s = 5

for its first few recusions,
cur[0] is [1,2]

when i is at val 3, 1+2+3=6 > s=5, then it will not go further dfs()
and i will not +1 anymore

so the case of returning False and trimming dfs tree
'''
class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        def dfs(i):
            if i == len(nums):
                return True
            for j in range(k): # for every bucket
                # if j => not 0
                if j and cur[j] == cur[j - 1]: # goal is k blocks all the same, so j must be same as j-1
                    continue
                cur[j] += nums[i] # for nums[i] to try every possible k partition

                # cannot be 'cur[j] == s', it will not enter follwing dfs() recursion
                if cur[j] <= s and dfs(i + 1):
                    return True
                cur[j] -= nums[i] # restore
            return False

        s, mod = divmod(sum(nums), k)
        if mod:
            return False
        cur = [0] * k
        nums.sort(reverse=True)
        # if reverse=False, or just no sort, then both will have error 'Time Limit Exceeded'
        # because, it's like the learning rate of ML-model training,
        # we want the initial step to be larger to reduce search times,
        # larger num will fail faster,
        # while smaller num will continue search on more recursions before failing
        return dfs(0)


'''
dynamic programming (DP) with bitmasking

It iterates through all possible bitmasks 
and updates the DP array dp based on the conditions of forming subsets with equal sums. 

It also keeps track of the current subset sum in the subset_sum array. 

Finally, it checks if the last element in the DP array is True, 
indicating that it's possible to partition the array into k equal sum subsets.
'''
class Solution: # dp version, OJ passed
    def canPartitionKSubsets(self, nums, k):
        total_sum = sum(nums)
        target_sum = total_sum // k
        
        if total_sum % k != 0 or max(nums) > target_sum:
            return False
        
        n = len(nums)
        dp = [False] * (1 << n)
        dp[0] = True
        
        subset_sum = [0] * (1 << n)
        
        for mask in range(1 << n):
            if not dp[mask]:
                continue
            for i in range(n):
                next_mask = mask | (1 << i)
                if mask & (1 << i) == 0 and subset_sum[mask] % target_sum + nums[i] <= target_sum:
                    dp[next_mask] = True
                    subset_sum[next_mask] = subset_sum[mask] + nums[i]
        
        return dp[(1 << n) - 1]

class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        @cache
        def dfs(state, t):
            if state == mask:
                return True
            for i, v in enumerate(nums):
                if (state >> i) & 1:
                    continue
                if t + v > s:
                    break
                if dfs(state | 1 << i, (t + v) % s):
                    return True
            return False

        s, mod = divmod(sum(nums), k)
        if mod:
            return False
        nums.sort()
        mask = (1 << len(nums)) - 1
        return dfs(0, 0)

#############

class Solution: # over time limit, no sorting
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        if nums is None or len(nums) == 0 or k <= 0:
            return False
        
        total_sum = sum(nums)
        if total_sum % k != 0:
            return False
        
        target = total_sum // k
        nums.sort()
        is_visited = [False] * len(nums)
        
        return self.dfs(0, 0, k, is_visited, target, nums)
    
    def dfs(self, start_index: int, current_sum: int, k: int, is_visited: List[bool], target: int, nums: List[int]) -> bool:
        if k == 1:
            return True
        if current_sum > target:
            return False
        if current_sum == target:
            return self.dfs(0, 0, k-1, is_visited, target, nums)
        
        for i in range(start_index, len(nums)):
            if is_visited[i]:
                continue
            
            is_visited[i] = True
            if self.dfs(i+1, current_sum+nums[i], k, is_visited, target, nums):
                return True
            is_visited[i] = False
        
        return False

############

class Solution:
    def canPartitionKSubsets(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        if not nums or len(nums) < k: return False
        _sum = sum(nums)
        div, mod = divmod(_sum, k)
        if _sum % k or max(nums) > _sum / k: return False
        nums.sort(reverse = True)
        target = [div] * k
        return self.dfs(nums, k, 0, target)
        
    def dfs(self, nums, k, index, target):
        if index == len(nums): return True
        num = nums[index]
        for i in range(k):
            if target[i] >= num:
                target[i] -= num
                if self.dfs(nums, k, index + 1, target): return True
                target[i] += num
        return False

func canPartitionKSubsets(nums []int, k int) bool {
	s := 0
	for _, v := range nums {
		s += v
	}
	if s%k != 0 {
		return false
	}
	s /= k
	cur := make([]int, k)
	n := len(nums)

	var dfs func(int) bool
	dfs = func(i int) bool {
		if i == n {
			return true
		}
		for j := 0; j < k; j++ {
			if j > 0 && cur[j] == cur[j-1] {
				continue
			}
			cur[j] += nums[i]
			if cur[j] <= s && dfs(i+1) {
				return true
			}
			cur[j] -= nums[i]
		}
		return false
	}

	sort.Sort(sort.Reverse(sort.IntSlice(nums)))
	return dfs(0)
}

function canPartitionKSubsets(nums: number[], k: number): boolean {
    let s = nums.reduce((a, b) => a + b);
    if (s % k !== 0) {
        return false;
    }
    s /= k;
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const f: boolean[] = new Array(1 << n).fill(false);
    f[0] = true;
    const cur: number[] = new Array(n).fill(0);
    for (let i = 0; i < 1 << n; ++i) {
        if (!f[i]) {
            continue;
        }
        for (let j = 0; j < n; ++j) {
            if (cur[i] + nums[j] > s) {
                break;
            }
            if (((i >> j) & 1) === 0) {
                f[i | (1 << j)] = true;
                cur[i | (1 << j)] = (cur[i] + nums[j]) % s;
            }
        }
    }
    return f[(1 << n) - 1];
}

698 - Partition to K Equal Sum Subsets

698. Partition to K Equal Sum Subsets

Level

Description

Solution

Using DP with Bit Masking

All Problems

All Solutions

Welcome to Subscribe On Youtube

698. Partition to K Equal Sum Subsets

Level

Description

Solution

Using DP with Bit Masking

All Problems

All Solutions