Leetcode 698 Solution

This article provides solution to leetcode question 698 (partition-to-k-equal-sum-subsets)
Categories:
Tags:
Access this page by simply typing in "lcs 698" in your browser address bar if you have bunnylol configured.

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)