LeetCode 2022.9.20 的打卡题目

698 划分为k个相等的子集 [https://leetcode.cn/problems/partition-to-k-equal-sum-subsets]

给定一个整数数组  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] 范围内

解法1 搜索剪枝

回溯法，枚举每个数字是否放进某个组里。
但是直接搜索会超时。
剪枝思路：

1. 从大到小对数字进行排序，这样有比较大的概率在 (targets[i] >= nums[current])这一步进行跳过；
2. 对于已经处理过的同样大小的组，如果当前数没有成功放进去，那它就不需要再次进行计算了，这一步剪枝可以使搜索算法通过此题。这里用unordered_set存储了一下已经废掉的解；网上题解多是使用targets[i] == targets[i - 1]来判断，好像会更快一些。

class Solution {
public:
    bool dfs(vector<int>& nums, vector<int>& targets, int current) {
        if (current == nums.size()) {
            for (int i = 0; i < targets.size(); ++i) {
                if (targets[i]) {
                    return false;
                }
            }
            return true;
        }

        unordered_set<int> unsolved;

        for (int i = 0; i < targets.size(); ++i) {
            if ((solved.find(targets[i]) == unsolved.end()) && targets[i] >= nums[current]) {
                targets[i] -= nums[current];
                if (dfs(nums, targets, current + 1)) {
                    return true;
                }
                targets[i] += nums[current];
                unsolved.insert(targets[i]);
            }
        }
        return false;
    }

    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = accumulate(begin(nums), end(nums), 0);
        if (sum % k != 0) {
            return false;
        }

        sort(begin(nums), end(nums), greater<int>());

        vector<int> targets(k, sum / k);
        return dfs(nums, targets, 0);
    }
};