Leetcode-698 划分为k个相同的子集

本文主要是介绍Leetcode-698 划分为k个相同的子集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 题目描述

698 划分为k个相同的子集

2. 解题思路

方法一：回溯+剪枝

1. 首先判断数组元素和是否能被k整除，若可以则记划分的每个子集的元素和为target；
2. 使用回溯的思想依次尝试将每一个元素加入到子集中，直到所有的元素均加入到子集中，说明可以划分为k个相同的子集，返回true，否则返回false；

优化策略

1. 对数组进行从大到小的排序，减少搜索次数；
2. 当当前元素加入子集后的值大于target时，直接跳过；
3. 若是当前子集与前一个子集值相同，说明当前路径已搜索过，直接跳过。

3. 代码实现（回溯+剪枝）

class Solution {
public:bool canPartitionKSubsets(vector<int>& nums, int k) {int sum = accumulate(nums.begin(), nums.end(), 0);if (sum % k != 0)return false;int target = sum / k;vector<int> bucket(k, 0);function<bool(int)> back_track = [&](int idx) -> bool {if (idx == nums.size()) {return true;}for (int i = 0; i < k; i++) {// 剪枝操作if (i > 0 && bucket[i] == bucket[i - 1])continue;// 剪枝操作if (bucket[i] + nums[idx] > target)continue;bucket[i] += nums[idx];if (back_track(idx + 1))return true;bucket[i] -= nums[idx];}return false;};// 将数组中元素按照从大到小的顺序排列sort(nums.begin(), nums.end(), [](int a, int b) { return a > b; });return back_track(0);}
};

这篇关于Leetcode-698 划分为k个相同的子集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---