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的獎章，謝謝大家