算法题总结-均等划分

原题
https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/submissions/
给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。[1 <= k <= len(nums) <= 16]
输入示例

nums = [4, 3, 2, 3, 5, 2, 1], k = 4

输出示例

True

官方解法:
核心在于回溯算法。回溯算法即，尝试是否能找到，如果能找到所有组合即返回，如果没找到，就返回上层递归，重新尝试新组合
解析：
1.每件物品能且仅能取一次，因此，肯定需要保存每次尝试组合时，物品的状态(因为后续必须要用到@cache提速 因此状态必须用二进制来判断从而使得状态变成单个数字)
2.由于每个物品都要尝试组合，因此，不能在取出一组就返回，因此，递归过程中，组合目标值必须通过取余运算，每次取完一组就重置(例如 19%19==0)
3.组合递归函数的特殊返回：
3.1 每件物品取完了 且目标值重置了[正常找到所有组合了]
3.2 for循环遍历过后没有找到正常的组合

源码：

class Solution:
    def __init__(self):
        self.value = 0
        self.minList = []
        pass
    
    @cache
    def recurisive(self,status:int,ratio:int)->bool:
        '''
        通过递归确定组合策略
        :param status: 每个数字的使用情况
        :param minList: 实际使用的数组
        :param ratio: 每次递归需要拼出来的值
        :param assemble: 上层已经拼出来的策略
        :return:
        '''
        if status==0 and ratio==0:
            return True
        for i in range(len(self.minList)):
            if ratio+self.minList[i]>self.value:
                continue
            if (status>>i) & 1:
                if self.recurisive(status-pow(2,i),int((ratio+self.minList[i])%self.value)):
                    return True
        return False

    def canPartitionKSubsets(self,nums:list[int],k:int)->bool:
        sumValue = sum(nums)
        if sumValue%k == 0:
            ratio = sumValue//k
            minList = []
            equalList = []
            for item in nums:
                if item<ratio:
                    minList.append(item)
                elif item==ratio:
                    equalList.append([item])
                else:
                    return False
            if len(equalList)==k:
                return True
            # 状态列表 1:未用 0:使用
            status = pow(2,len(minList))-1
            # 排序 首先确定最大值对应的策略[如果先确定最小值的策略 最大值很大可能拼不出来 例如 ratio=19 [1,1,1,.....,18]]
            minList.sort()
            self.minList = minList[::-1]
            self.value = ratio
            # 如果并不是一个数字一个策略 那么就肯定需要排列组合来确定
            out = self.recurisive(status,0)
            return out
        else:
            return False