698. 划分为k个相等的子集

Difficulty
Medium
Tags
回溯
DFS
URL
https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/
Star
给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
示例 1：
输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
输出： True
说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。
示例 2:
输入: nums = [1,2,3,4], k = 3
输出: false
提示：
  • 1 <= k <= len(nums) <= 16
  • 0 < nums[i] < 10000
  • 每个元素的频率在 [1,4] 范围内

DFS

思路
使用k个桶的视角，对于每个桶，都要遍历 nums 中的 n 个数字，然后选择是否将当前遍历到的数字装进自己这个桶里。
1.使用backtrack时候的几个变量:
k: num of subsets
bucket: current bucket number
nums: arry contains of balls number
target: the target bucket size value
used: if this bucket used or not (bool)
hashmap: to storage used status to avoid unnecessary traverse
  1. 为了优化不必要的重复检索, 比如1,4,2,3 选了(1,4)(2,3) 和(2,3)(1,4)的结果一样只是顺序不同, 使用hashmap来优化去掉这些重复的pattern
  1. 注意题目给的数据规模 nums.length <= 16，也就是说 used 数组最多也不会超过 16，那么我们完全可以用「位图」的技巧，用一个 int 类型的 used 变量来替代 used 数组。
优化：
  1. 遇到超过target 的数字，说明不能放到任意一个桶中，直接return False
  1. 将数组逆序排序，让大数字先放进去，可以减少很多不必要的情况
  1. 用 hash 来存储 每个满足 target 的桶中的情况
  1. 用 位 来存储使用过的数字
时间复杂度:
每个桶要遍历 n 个数字，对每个数字有「装入」或「不装入」两种选择，所以组合的结果有 2^n 种；而我们有 k 个桶，所以总的时间复杂度为 O(k*2^n)
题解
class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        if len(nums) < k: return False
        if sum(nums) % k != 0: return False

        target = sum(nums) // k 
        used = 0 
        hashmap = set()
        nums.sort(reverse=True)
        return self.backtrack(k, 0, nums, 0, target, used, hashmap)
    
    
    def backtrack(self, k, bucket, nums, start, target, used, hashmap):
        """
        k: num of subsets
        bucket: current bucket number
        nums: arry contains of balls number
        target: the target bucket size value
        used: if this bucket used or not (bool)
        hashmap: to storage used status to avoid unnecessary traverse  
        """
        if k == 0: return True
        if bucket == target:
            # 之前用过的状态肯定是 False 的
            if used in hashmap:
                return False
            hashmap.add(used)
            # 开始 新的一个桶， 新桶要从 nums[0] 开始搜索
            return  self.backtrack(k - 1, 0, nums, 0, target, used, hashmap)
        
        for i in range(start, len(nums)):
            if (used >> i & 1) == 1:
                continue 
            
            if nums[i] + bucket > target:
                continue

            used |= (1 << i)
            bucket += nums[i]
            if self.backtrack(k, bucket, nums, i + 1, target, used, hashmap):
                return True
            used ^= (1 << i)
            bucket -= nums[i]

        return False