LeetCode698 划分为k个相等的子集

发表于 | 分类于 |
字数统计: 356 | 阅读时长 ≈ 1

链接: https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/

题意

给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。

解法

考虑搜索 + 剪枝
其中有一些基础的优化 例如判断最后是否满足条件可以用cnt变量来记录个数
然后将数组由大到小进行排序
还有很神奇的一句话
if (i > 0 && state[i] == state[i - 1]) continue;
不加超时 加了打败92%
如果下一个的值和当前的值是一样的话
那之前回溯了说明不满足条件
那这个也一定不行
所以直接跳过

代码

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
class Solution {
public:
    bool ans;
    void dfs(int loc, vector<int>& state, int target, vector<int>& nums, int cnt) {
        if (ans) {
            return;
        }
        if (loc == nums.size()) {
            if (cnt == state.size())
                ans = true;
            return;
        }
        for (int i = 0; i < state.size(); i++) {
            if (i > 0 && state[i] == state[i - 1]) continue;
            if (state[i] + nums[loc] < target) {
                state[i] += nums[loc];
                dfs(loc + 1, state, target, nums, cnt);
                state[i] -= nums[loc];
            }
            else if (state[i] + nums[loc] == target) {
                state[i] += nums[loc];
                dfs(loc + 1, state, target, nums, cnt + 1);
                state[i] -= nums[loc];
            }
        }
    }
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = 0;
        sort(nums.begin(), nums.end(), greater<int>());
        for (int i: nums) {
            sum += i;
        }
        if (sum % k) return false;
        vector<int> state(k);
        dfs(0, state, sum / k, nums, 0);
        return ans;
    }
};