代码

版本1 nonlocal

class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        nums.sort()
        # print(nums)
        avg = sum(nums)//k
        if sum(nums)/k != avg:
            return False

        vis = set()
        result = False

        # @cache
        def solve(val, curr):
            if curr in vis:
                return
            if curr == 0:
                nonlocal result
                result = True
            vis.add(curr)
            for i in range(0, len(nums)):
                if val + nums[i] > avg:
                        break
                if curr >> i & 1 and solve((val+nums[i]) % avg, curr ^ (1<<i)):
                    result = True
            return False

        solve(0, (1<<(len(nums))) - 1)

        return result

版本2 无nonlocal

class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        nums.sort()
        # print(nums)
        avg = sum(nums)//k
        if sum(nums)/k != avg:
            return False

        vis = set()

        # @cache
        def solve(val, curr):
            if curr in vis:
                return
            if curr == 0:
                return True
            vis.add(curr)
            for i in range(0, len(nums)):
                if val + nums[i] > avg:
                        break
                if curr >> i & 1 and solve((val+nums[i]) % avg, curr ^ (1<<i)):
                    return True
            return False

        return solve(0, (1<<(len(nums))) - 1)

性能对比

版本1

file

版本2

file

最后修改日期: 2022年9月21日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。