https://leetcode.com/problems/partition-to-k-equal-sum-subsets/
將陣列(nums)中的數字分組,分k組,每組加總值必須一樣。
每組(subset)加總值為sum(nums)/k
條件:加某一element沒有超過subset的sum則往下一element走(recursive)
有超過則不加入組裡,往下組加看看
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)
Medium