698. Partition to K Equal Sum Subsets LeetCode Solution
In this guide, you will get 698. Partition to K Equal Sum Subsets LeetCode Solution with the best time and space complexity. The solution to Partition to K Equal Sum Subsets problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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 <= 16
1 <= nums[i] <= 104
The frequency of each element is in the range [1, 4].
Complexity Analysis
Time Complexity: O(2^n)
Space Complexity: O(n)
698. Partition to K Equal Sum Subsets LeetCode Solution in C++
class Solution {
public:
bool canPartitionKSubsets(vector<int>& nums, int k) {
const int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum % k != 0)
return false;
const int target = sum / k; // the target sum of each subset
if (ranges::any_of(nums, [target](const int num) { return num > target; }))
return false;
ranges::sort(nums, greater<>());
return dfs(nums, 0, k, /*currSum=*/0, target, /*used=*/0);
}
private:
bool dfs(const vector<int>& nums, int s, int remainingGroups, int currSum,
const int subsetTargetSum, int used) {
if (remainingGroups == 0)
return true;
if (currSum > subsetTargetSum)
return false;
if (currSum == subsetTargetSum) // Find a valid group, so fresh start.
return dfs(nums, 0, remainingGroups - 1, 0, subsetTargetSum, used);
for (int i = s; i < nums.size(); ++i) {
if (used >> i & 1)
continue;
if (dfs(nums, i + 1, remainingGroups, currSum + nums[i], subsetTargetSum,
used | 1 << i))
return true;
}
return false;
}
}; /* code provided by PROGIEZ */
698. Partition to K Equal Sum Subsets LeetCode Solution in Java
class Solution {
public boolean canPartitionKSubsets(int[] nums, int k) {
final int sum = Arrays.stream(nums).sum();
if (sum % k != 0)
return false;
final int target = sum / k; // the target sum of each subset
if (Arrays.stream(nums).anyMatch(num -> num > target))
return false;
return dfs(nums, 0, k, /*currSum=*/0, target, /*used=*/0);
}
private boolean dfs(int[] nums, int s, int remainingGroups, int currSum, int subsetTargetSum,
int used) {
if (remainingGroups == 0)
return true;
if (currSum > subsetTargetSum)
return false;
if (currSum == subsetTargetSum) // Find a valid group, so fresh start.
return dfs(nums, 0, remainingGroups - 1, 0, subsetTargetSum, used);
for (int i = s; i < nums.length; ++i) {
if ((used >> i & 1) == 1)
continue;
if (dfs(nums, i + 1, remainingGroups, currSum + nums[i], subsetTargetSum, used | 1 << i))
return true;
}
return false;
}
} // code provided by PROGIEZ
698. Partition to K Equal Sum Subsets LeetCode Solution in Python
class Solution:
def canPartitionKSubsets(self, nums: list[int], k: int) -> bool:
summ = sum(nums)
if summ % k != 0:
return False
target = summ // k # the target sum of each subset
if any(num > target for num in nums):
return False
def dfs(s: int, remainingGroups: int, currSum: int, used: int) -> bool:
if remainingGroups == 0:
return True
if currSum > target:
return False
if currSum == target: # Find a valid group, so fresh start.
return dfs(0, remainingGroups - 1, 0, used)
for i in range(s, len(nums)):
if used >> i & 1:
continue
if dfs(i + 1, remainingGroups, currSum + nums[i], used | 1 << i):
return True
return False
nums.sort(reverse=True)
return dfs(0, k, 0, 0) # code by PROGIEZ
