##### Welcome to Subscribe On Youtube

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.

#### Using DP with Bit Masking

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
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):
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:

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