Cinte's Leetcode Record
0%

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

Posted on Edited on In Disqus:
Symbols count in article: 2.6k Reading time ≈ 2 mins.

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

参考经典回溯算法：集合划分问题「重要更新 🔥🔥🔥」

球来选择桶

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        auto sum = accumulate(nums.begin(), nums.end(), 0);
        if(sum % k != 0)
            return false;
        sum /= k;
        // 排列，从大到小排，是为了让回溯过程更早地触发剪枝条件，越早剪枝，剪掉的小枝就越多
        sort(nums.begin(), nums.end(), greater<int>());
        vector<int> buckets(k);
        return helper(nums, buckets, 0, sum);
    }

private:
    bool helper(vector<int> &nums, vector<int> &buckets, int index, int target) {
        // 当所有球都被用完了，说明所有球都各个放入桶中，并且由于bucket + nums[index] > target约束地存在，说明所有桶的和都为target，所以返回true
        if(index == nums.size())
            return true;
        // 下标为index的小球选择自己要去哪个桶。对桶进行遍历。如果一个桶都容不下他了，就得递归返回了，让前面去修复。
        for(int i = 0; i < buckets.size(); ++i) {
            auto &bucket = buckets[i];
            // 如果放入后的和>target了，说明不能放
            if(bucket + nums[index] > target)
                continue;
            // 如果前一个桶的和和现在的桶一样，由于桶本身是没有顺序标号的，所以选择前一个桶和选择当前桶的结果一样，所以为了减少无用功，跳过。
            if(i > 0 && buckets[i - 1] == bucket)
                continue;
            // 与上述原因相同，第一个球始终让他进第一个桶，没必要重复操作。
            if(index == 0 && i > 0)
                break;
            // 球入桶
            bucket += nums[index];
            // 让下一个球选
            if(helper(nums, buckets, index + 1, target))
                return true;
            // 回溯，球出桶
            bucket -= nums[index];
        }
        return false;
    }
};

桶来选择球

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        auto sum = accumulate(nums.begin(), nums.end(), 0);
        if(sum % k != 0)
            return false;
        sum /= k;
        // 从大到小排，更快剪枝
        sort(nums.begin(), nums.end(), greater<int>());
        vector<int> buckets(k);
        return helper(nums, buckets, 0, 0, sum, k - 1);
    }

private:
    // 来记录一个桶被装满时候，接下来的路能不能到达。防止重复走这种状态
    unordered_map<int, bool> memo;
    bool helper(vector<int> &nums, vector<int> &buckets, int visited, int index, int target, int cur_level) {
        // 当桶全都装了，那就说明能装
        if(cur_level < 0)
            return true;
        // 当前桶被装满了
        if(buckets[cur_level] == target) {
            // 看看当前桶在这种选择下被装满的情况下，能否
            auto r = helper(nums, buckets, visited, 0, target, cur_level - 1);
            // 记录当前状态，免得别的桶也走到了
            memo.emplace(visited, r);
            return r;
        }
        // 如果当前状态走过，由于桶是无序的所以直接返回
        if(memo.count(visited))
            return memo.at(visited);
        for(int i = index; i < nums.size(); ++i) {
            // 球用过了，pass
            if((1 << i) & visited)
                continue;
            // 放不下这个球，pass
            if(buckets[cur_level] + nums[i] > target)
                continue;
            buckets[cur_level] += nums[i];
            visited ^= 1 << i;
            // 让下一个球来选，同时也会根据情况进行下一个桶的判断
            if(helper(nums, buckets, visited, i + 1, target, cur_level))
                return true;
            buckets[cur_level] -= nums[i];
            visited ^= 1 << i;
            // 如果下一个球和当前球数值相同，由于当前球已经返回了，且包含了下一个球能包含的所有情况，所以直接跳过（需要在有序的前提下）
            if(i < nums.size() - 1 && nums[i] == nums[i + 1])
                ++i;
        }
        return false;
    }

};