Algorithm
Problem Name: 698. Partition to K Equal Sum Subsets
Given an integer array nums and an integer k, return true if it is 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 is possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.
Example 2:
Input: nums = [1,2,3,4], k = 3 Output: false
Constraints:
1 <= k <= nums.length <= 161 <= nums[i] <= 104- The frequency of each element is in the range
[1, 4].
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const canPartitionKSubsets = function(nums, k) {
const sum = nums.reduce((ac, el) => ac + el, 0)
return k !== 0 && sum % k === 0 && canPartition(0, nums, [], k, 0, sum / k)
};
function canPartition(start, nums, seen, k, sum, target) {
if(k === 1) return true
if (sum === target) {
return canPartition(0, nums, seen, k - 1, 0, target)
}
for(let i = start; i < nums.length; i++) {
if (!seen[i]) {
seen[i] = true
if(canPartition(i + 1, nums, seen, k, sum + nums[i], target)> {
return true
}
seen[i] = false
}
}
return false
}
Input
nums = [4,3,2,3,5,2,1], k = 4
Output
true
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def canPartitionKSubsets(self, nums, k):
def dfs(i, sums):
if i == n:
return True
for j in range(k):
if sums[j] + nums[i] <= target:
sums[j] += nums[i]
if dfs(i + 1, sums):
return True
sums[j] -= nums[i]
return False
nums.sort(reverse = True)
sm = sum(nums)
if sm % k: return False
target, n = sm // k, len(nums)
return dfs(0, [0] * k)
Input
nums = [4,3,2,3,5,2,1], k = 4
Output
true
#3 Code Example with C# Programming
Code -
C# Programming
using System;
namespace LeetCode
{
public class _0698_PartitionToKEqualSumSubsets
{
public bool CanPartitionKSubsets(int[] nums, int k)
{
int sum = 0, max = int.MinValue;
foreach (var num in nums)
{
sum += num;
max = Math.Max(max, num);
}
if (max > sum / k || sum % k != 0) return false;
return CanPartitionKSubsets(nums, k, new bool[nums.Length], sum / k, 0, 0);
}
private bool CanPartitionKSubsets(int[] nums, int k, bool[] visited, int target, int current, int index)
{
if (k == 1) return true;
if (target == current)
return CanPartitionKSubsets(nums, k - 1, visited, target, 0, 0);
for (int i = index; i < nums.Length; i++)
{
if (visited[i]) continue;
if (current + nums[i] > target) continue;
visited[i] = true;
if (CanPartitionKSubsets(nums, k, visited, target, current + nums[i], i + 1))
return true;
visited[i] = false;
}
return false;
}
}
}
Input
nums = [1,2,3,4], k = 3
Output
false