tags: 阿瑜

Day 16: LeetCode 698. Partition to K Equal Sum Subsets

Source

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

1.題意:

將陣列(nums)中的數字分組，分k組，每組加總值必須一樣。

2.思路:

每組(subset)加總值為sum(nums)/k
條件:加某一element沒有超過subset的sum則往下一element走(recursive)
有超過則不加入組裡，往下組加看看

3.程式碼:

class Solution(object):
    def canPartitionKSubsets(self, nums, k):
        sums = [0]*k
        subsum = sum(nums) / k
        nums.sort(reverse=True)
        l = len(nums)
        
        def walk(i):
            if i == l:
                return len(set(sums)) == 1
            for j in xrange(k):
                sums[j] += nums[i]
                if sums[j] <= subsum and walk(i+1):
                    return True
                sums[j] -= nums[i]
                if sums[j] == 0:
                    break
            return False
            
        '''加上會比較慢
        if sum(nums)%k!=0:
            return False
        '''
        return walk(0)

Level:Medium