class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        S = sum(nums)
        if S % k != 0:
            return False

        target = S // k
        nums.sort(reverse=True)
        if nums[0] > target:
            return False

        values = [0] * k
        def recurse(cur_idx: int, num_subsets: int) -> bool:
            if cur_idx == len(nums):
                return True

            cur = nums[cur_idx]
            for i in range(min(k, num_subsets + 1)):
                if values[i] + cur <= target:
                    values[i] += cur
                    if recurse(cur_idx + 1, max(num_subsets, i + 1)):
                        return True
                    values[i] -= cur
            return False

        values[0] = nums[0]
        return recurse(1, 1)