Leetcode 698 Solution

This article provides solution to leetcode question 698 (partition-to-k-equal-sum-subsets)

https://leetcode.com/problems/partition-to-k-equal-sum-subsets

Solution

class Solution: def canPartitionKSubsets(self, nums: List[int], k: int) -> bool: if sum(nums) % k: return False
nums = list(reversed(sorted(nums)))
t = sum(nums) // k group_sums = [0] * k
def dfs(nums, i): if i == len(nums): return True
for c in range(k): if group_sums[c] + nums[i] <= t: group_sums[c] += nums[i] if dfs(nums, i + 1): return True group_sums[c] -= nums[i] return False
return dfs(nums, 0)