698. Partition to K Equal Sum Subsets

https://leetcode.com/problems/partition-to-k-equal-sum-subsets/

题目解释

给你一组数字阵列nums和数字k，如果能把阵列分成k个不为空的子集且子集内的合相等就回传True

example

解法

今天的题目在Related Topics提到能用DP也能用Backtracking，不过我想不到DP的解法，所以就用Backtracking来解吧

首先，我们要判断他给的阵列能不能切成每个合相等的子集，所以先出每个子集的合target，并且要符合下面两个规则:

1. 阵列nums要能被数字k整除
2. 阵列nums的最大值不能大於子集的合target

接着就是用回朔法了:

我的想法是一项一项组合出target把k慢慢消耗掉，所以终止条件是k = 0

再来，组合会有两种状况:

1. 新加进来的数字让合刚好等於target，这时候我们继续做下一圈的递回backtracking(0, k-1)
2. 新加进来的数字让合小於target，这时候我们判断之後的递回能不能组合出target，不行的话也别让它占着数字

程序码

class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        
        def backtracking(curr, k):
            
            if k == 0: return True
            
            for i in range(len(nums)):
                
                if used[i]: continue
                    
                if curr + nums[i] == target:
                # 可以消耗掉1个k
                    used[i] = True
                    return backtracking(0, k-1)
                
                elif curr + nums[i] < target:
                # 由後续判断能不能组成target
                    used[i] = True
                    
                    if backtracking(curr + nums[i], k):
                        return True
                    
                    else:
                        used[i] = False
            
            return False

        
        if sum(nums) % k != 0: return False
        
        target = sum(nums) // k
        nums.sort(reverse=True)        
        if nums[0] > target: return False
        
        used = [False] * len(nums)
        # 标注哪些数字用过了
        
        return backtracking(0, k)

闲聊

今天30天完赛了，Sep LeetCoding Challenge也结束了

虽然很多hard难度的题目都是看着答案打的，不过还能得到完成奖章

这就是LeetCoding Challenge的奖章，谢谢大家