698. Partition to K Equal Sum Subsets (Medium) - TengnanYao/daily_leetcode GitHub Wiki

class Solution(object):
    def canPartitionKSubsets(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        s = sum(nums)
        if s % k:
            return False
        target = s // k
        n = len(nums)
        result = []
        def helper(arr, s):
            if s == target:
                result.append(arr)
            for i in range(arr[-1] + 1 if arr else 0, n):
                if nums[i] + s <= target:
                    helper(arr + [i], nums[i] + s)
        helper([], 0)
        for comb in list(itertools.combinations(result, k)):
            arr = sum(comb, [])
            if len(set(arr)) == len(arr):
                return True
        return False