<jupyter_start><jupyter_text>给定一个由整数nums和正整数k组成的数组，请确定是否有可能将此数组划分为k个非空子集，它们的总和都相等。    1、所有的数字都必须要用到           例1：        Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4        Output: True        Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.<jupyter_code>class Solution:
    def canPartitionKSubsets(self, nums, k: int) -> bool:
        if len(nums) < k or sum(nums) % k != 0: return False
        nums.sort()
        mean_val = sum(nums) // k
        
        # 检查数组中，是否存在比 mean_val更大的值，如果有，则为False
        for i in range(len(nums) - 1, -1, -1):
            if nums[i] > mean_val:
                return False
        
        # 这个时候，数组中最大的数字，一定是小于等于target的，如果正好等于target
        # 则需要遍历 nums 的位数就少了一位，k也相应的减少
        start_index = len(nums) - 1
        while start_index >= 0 and nums[start_index] == mean_val:
            start_index -= 1
            k -= 1
        return self.partition([0] * k, nums, start_index, mean_val)
    
    def partition(self, subset, nums_, index, target):
        if index < 0:
            return True
        
        val = nums_[index]
        for i in range(len(subset)):
            if val + subset[i] <= target:
                subset[i] += val
                # subset[i] + val 小于等于 target 的时候，可以放入，此时，需要计算，
                # 剩余的数组能否返回True，如果不能，则需要返回原始的状态
                if self.partition(subset, nums_, index-1, target):
                    return True
                else:
                    subset[i] -= val
        return False
class Solution:
    def canPartitionKSubsets(self, nums, k: int) -> bool:
        if len(nums) < k or sum(nums) % k != 0: return False
        target_val = sum(nums) // k
        nums.sort()
        
        for i in range(len(nums)-1, -1, -1):
            if nums[i] > target_val:
                return False
        
        start_index = len(nums) - 1
        while start_index >= 0 and nums[start_index] == target_val:
            start_index -= 1
            k -= 1
        
        return self.recursion([0]*k, nums, start_index, target_val)
    
    def recursion(self, subset, nums_, index, target):
        if index < 0: return True
        
        val = nums_[index]
        for i in range(len(subset)):
            if val + subset[i] <= target:
                subset[i] += val
                if self.recursion(subset, nums_, index-1, target):
                    return True
                else:
                    subset[i] -= val
        return False
nums_ = [2,2,2,2,3,4,5]
k_ = 4
solution = Solution()
solution.canPartitionKSubsets(nums_, k_)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1113662456946039, 'fraction_numerical': 0.018369690011481057, 'mean_word_length': 1.6782786885245902, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '521649', 'license': 'Apache-2.0', 'n_tokens_mistral': 987, 'n_tokens_neox': 955, 'n_words': 224, 'path': 'Dynamic Programming/0801/698. Partition to K Equal Sum Subsets.ipynb', 'repo_name': 'YuHe0108/Leetcode', 'size': '2613'}