Leetcode 698:划分为k个相等的子集(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 698:划分为k个相等的子集(超详细的解法!!!)

in leetcode with 0 comment

给定一个整数数组nums和一个正整数k,找出是否有可能把这个数组分成k个非空子集,其总和都相等。

示例 1:

输入: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
输出: True
说明: 有可能将其分成 4 个子集(5),(1,4),(2,3),(2,3)等于总和。

注意:

解题思路

这个问题实际上和Leetcode 473:火柴拼正方形是一样的,之前问题相当于k=4的情况,只要将代码稍加修改即可。

class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        s, n = sum(nums), len(nums)
        if s % k:
            return False
        
        t = s//k
        nums.sort(reverse=True)
        vis = [0] * n
        
        def dfs(cur, u, p):
            if u == k: return True
            if cur == t: return dfs(0, u + 1, 0)
            
            i = p
            while i < n:
                if vis[i] or (cur + nums[i] > t): 
                    i += 1
                    continue
                    
                vis[i] = 1
                if dfs(cur + nums[i], u, i + 1): return True
                vis[i] = 0
                
                if not cur or cur + nums[i] == t: return False 
                
                j = i
                while j < n and nums[i] == nums[j]: j += 1 
                i = j - 1
                i += 1
            return False
        
        return dfs(0, 0, 0)

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses