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

链接：698.划分为k个相等的子集
难度：Medium
标签：位运算、记忆化搜索、数组、动态规划、回溯、状态压缩
简介：给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。

题解 1 - cpp

• 编辑时间：2022-09-20
• 执行用时：4ms
• 内存消耗：9MB
• 编程语言：cpp
• 解法介绍：构造 k 个桶进行回溯+剪枝。

class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        sort(nums.rbegin(), nums.rend());
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % k != 0) return false; else sum /= k;
        vector<int> list(k, 0);
        return dfs(nums, list, sum, 0);
    }
    bool dfs(vector<int> &nums, vector<int> &list, int sum, int i) {
        if (i == nums.size()) {
            for (auto &item : list) if (item != sum) return false;
            return true;
        }
        for (int j = 0; j < list.size(); j++) {
            if (list[j] + nums[i] > sum || j && list[j - 1] == list[j]) continue;
            list[j] += nums[i];
            if (dfs(nums, list, sum, i + 1)) return true;
            list[j] -= nums[i];
        }
        return false;
    }
};

题解 2 - python

• 编辑时间：2024-08-25
• 执行用时：521ms
• 内存消耗：48.65MB
• 编程语言：python
• 解法介绍：记忆化递归，同时利用二进制记录是否被使用。

class Solution:
    def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
        nsum = sum(nums)
        if nsum % k != 0: return False
        vnum = nsum // k
        n = len(nums)
        @cache
        def dfs(idx: int, val: int, mask: int) -> bool:
            if val == vnum: return dfs(idx + 1, 0, mask)
            if idx == k: return mask == 0
            for i in range(n):
                if ((mask >> i) & 1) and \
                    val + nums[i] <= vnum and \
                    dfs(idx, val + nums[i], mask & ~(1 << i)):
                    return True
            return False
        return dfs(0, 0, (1 << n) - 1)