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