Learning On the Way

698. Partition to K Equal Sum Subsets

Given an array of integers nums and a positive integer k, find whether it's possible to divide this array into k non-empty subsets whose sums are all equal.

def canPartitionKSubsets(self, nums: List[int], k: int) -> bool: 
    target = sum(nums) // k 
    nums.sort(reverse=True) 
    if sum(nums) % k > 0: 
        return False 
     
    if nums[0] > target: 
        return False 
     
    groupsum = [0] * k 
    found = False 
     
    def backtrack(idx): 
        nonlocal found 
         
        if found: 
            return 
                    
        for i in range(k): 
            if found: 
                return 
             
            if nums[idx] + groupsum[i] <= target: 
                groupsum[i] += nums[idx] 
                if idx == len(nums) - 1: 
                    found = True 
                    return 
                 
                backtrack(idx + 1) 
                 
                groupsum[i] -= nums[idx] 
                 
                if groupsum[i] == 0: 
                    break 
                     
    backtrack(0)     
    return found