LeetCode 698 Partition to K Equal Sum Subsets

标签: 回溯法 LeetCode 发布于:2022-02-22 11:35:45 编辑于:2022-02-22 14:42:25 浏览量:364

概述

https://leetcode.com/problems/partition-to-k-equal-sum-subsets/

回溯法(以数字的视角)

每次选择我们凑出一个满足要求的子集?但是好麻烦啊。

https://labuladong.gitee.io/algo/4/29/111/

这里给的思路是,维护 k 个桶,然后每个数字选择桶。

class Solution {
public:
    int t;
    int k;
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        this->k = k;
        int sum = 0;
        for (auto& num : nums) sum += num;
        if (sum % k != 0) return false;
        t = sum / k;
        vector<int> buckets(k, 0);
        return backtrack(nums, buckets, 0);
    }
    
    bool backtrack(vector<int>& nums, vector<int>& buckets, int c) {
        if (c == nums.size()) {
            for (auto& b : buckets) {
                if (b != t) return false;
            }
            return true;
        }
        for (auto& b : buckets) {
            b += nums[c];
            if (backtrack(nums, buckets, c + 1)) return true;
            b -= nums[c];
        }
        return false;
    }
};

TLE 了(37 / 159 test cases passed)。

加个小优化:if (b + nums[c] > t) continue;

又 TLE 了(54 / 159 test cases passed)。。

对数字降序排序,这样可以提早触发早停的 if 分支。

又又 TLE 了(151 / 159 test cases passed)。。。

回溯法(以桶的视角)

class Solution {
public:
    int t;
    int k;
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        this->k = k;
        int sum = 0;
        for (auto& num : nums) sum += num;
        if (sum % k != 0) return false;
        t = sum / k;
        vector<int> used(nums.size(), false);
        sort(nums.begin(), nums.end());
        return backtrack(nums, used, 0, 0);
    }
    
    bool backtrack(vector<int>& nums, vector<int>& used, int c, int idx) {
        if (idx == k) {
            return true;
        }
        for (int i = 0; i < nums.size(); i ++) {
            if (used[i]) continue;
            if (c + nums[i] > t) break;
            used[i] = true;
            if (c + nums[i] == t) {
                if (backtrack(nums, used, 0, idx + 1)) return true;
            } else {
                if (backtrack(nums, used, c + nums[i], idx)) return true;
            }
            used[i] = false;
        }
        return false;
    }
};

好家伙,又 TLE 了,给我整无语了属于是。

不玩了,花了好久了。

未经允许,禁止转载,本文源站链接:https://iamazing.cn/