↓Skip to main content
  1. Posts/

LeetCode-698 划分为k个相等的子集

·1 min·
Table of Contents

LeetCode-698 划分为k个相等的子集 #

Solution 1 #

状压 dp.

代码如下:

class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        if sum(nums) % k != 0:
            return False
        t = sum(nums) // k
        n = len(nums)
        nums.sort()
        @cache
        def f(mask, s, i): 
            if mask == (1 << n) - 1:
                return True
            for i in range(n):
                if mask & (1 << i) == 0:
                    if s + nums[i] == t:
                        if f(mask | (1 << i), 0, i + 1):
                            return True
                    elif s + nums[i] < t:
                        if f(mask | (1 << i), s + nums[i], i):
                            return True
                    else:
                        break
            return False
        return f(0, 0, 1)