【力扣】划分为k个相等的子集

2024-08-29 00:04
文章标签 力扣 子集 划分 相等

本文主要是介绍【力扣】划分为k个相等的子集,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

  🔥博客主页: 我要成为C++领域大神
🎥系列专栏:【C++核心编程】 【计算机网络】 【Linux编程】 【操作系统】
❤️感谢大家点赞👍收藏⭐评论✍️

本博客致力于知识分享,与更多的人进行学习交流

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

回溯+剪枝

思路

首先计算数组的所有元素的总和,如果这个总和不能被 k 整除,则无法划分,直接返回 false

对数组进行逆序排序,尽可能先处理较大的元素,可以提前不可行的情况。

通过DFS结合回溯,将每个元素分配到某个子集中。通过剪枝操作,避免重复计算无效路径。

从第 0 个元素开始调用 dfs,并返回结果。

代码实现

class Solution {
public:bool canPartitionKSubsets(vector<int>& nums, int k) {int sum = accumulate(nums.begin(), nums.end(), 0);if (sum % k)return false;sum /= k;                         // 子集的总和sort(nums.rbegin(), nums.rend()); // 逆序排序if (nums[0] > sum)return false;vector<int> SubSum(k, 0);function<bool(int)> dfs = [&](int i) {if (i == nums.size())return true;for (int j = 0; j < k; ++j) {if (j && SubSum[j] == SubSum[j - 1])continue; // 剪枝操作if (nums[i] + SubSum[j] <= sum) {SubSum[j] += nums[i];if (dfs(i + 1))return true;SubSum[j] -= nums[i];}}return false;};return dfs(0);}
};

这篇关于【力扣】划分为k个相等的子集的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1116266

相关文章

poj 2104 and hdu 2665 划分树模板入门题

题意: 给一个数组n(1e5)个数,给一个范围(fr, to, k),求这个范围中第k大的数。 解析: 划分树入门。 bing神的模板。 坑爹的地方是把-l 看成了-1........ 一直re。 代码: poj 2104: #include <iostream>#include <cstdio>#include <cstdlib>#include <al

Thread如何划分为Warp?

1 .Thread如何划分为Warp? https://jielahou.com/code/cuda/thread-to-warp.html  Thread Index和Thread ID之间有什么关系呢?(线程架构参考这里:CUDA C++ Programming Guide (nvidia.com)open in new window) 1维的Thread Index,其Thread

两数之和--力扣1

两数之和 题目思路C++代码 题目 思路 根据题目要求,元素不能重复且不需要排序,我们这里使用哈希表unordered_map。注意题目说了只对应一种答案。 所以我们在循环中,使用目标值减去当前循环的nums[i],得到差值,如果我们在map中能够找到这个差值,就说明存在两个整数的和为目标值。 如果没有找到,就将当前循环的nums[i]以及下标i放入map中,以便后续查

力扣第347题 前K个高频元素

前言 记录一下刷题历程 力扣第347题 前K个高频元素 前K个高频元素 原题目: 分析 我们首先使用哈希表来统计数字出现的频率,然后我们使用一个桶排序。我们首先定义一个长度为n+1的数组,对于下图这个示例就是长度为7的数组。为什么需要一个长度为n+1的数组呢?假如说总共有三个数字都为1,那么我们需要把这个1放在数组下标为3的位置,假如说数组长度为n,对于这个例子就是长度为3,那么它的

【数据结构与算法 | 灵神题单 | 删除链表篇】力扣3217, 82, 237

总结,删除链表节点问题使用到列表,哈希表,递归比较容易超时,我觉得使用计数排序比较稳,处理起来也不是很难。 1. 力扣3217:从链表中移除在数组中的节点 1.1 题目: 给你一个整数数组 nums 和一个链表的头节点 head。从链表中移除所有存在于 nums 中的节点后,返回修改后的链表的头节点。 示例 1: 输入: nums = [1,2,3], head = [1,2,3,

力扣 739. 每日温度【经典单调栈题目】

1. 题目 理解题意: 1.1. 给一个温度集合, 要返回一个对应长度的结果集合, 这个结果集合里面的元素 i 是 当前 i 位置的元素的下一个更高温度的元素的位置和当前 i 位置的距离之差, 若是当前元素不存在下一个更高温度的元素, 则这个位置用0代替; 2. 思路 本题用单调栈来求解;单调栈就适用于来求当前元素左边或者右边第一个比当前元素大或者小的元素;【单调栈:让栈中的元素保持单调

力扣接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例 1: 输入:height = [0,1,0,2,1,0,1,3,2,1,2,1]输出:6解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 示例 2: 输入:height

每日一题,力扣leetcode Hot100之238.除自身以外数组的乘积

乍一看这个题很简单,但是不能用除法,并且在O(N)时间复杂度完成或许有点难度。 考虑到不能用除法,如果我们要计算输出结果位置i的值,我们就要获取这个位置左边的乘积和右边的乘积,那么我新设立两个数组L和R。 对于L来说,由于表达的是位置i左边的数的乘积,那么L[0]=1,因为第一个数字左边没数那么为了不影响乘积初始值就设置为1,那么L[1]=L[0]*nums[0],那么L[i]=L[i-1

代码随想录刷题day24丨93.复原IP地址 ,78.子集 , 90.子集II

代码随想录刷题day24丨93.复原IP地址 ,78.子集 , 90.子集II 1.题目 1.1复原IP地址 题目链接:93. 复原 IP 地址 - 力扣(LeetCode) 视频讲解:回溯算法如何分割字符串并判断是合法IP?| LeetCode:93.复原IP地址_哔哩哔哩_bilibili 文档讲解:https://programmercarl.com/0093.%E5%A4%8

【电子通识】洁净度等级划分及等级标准

洁净度常用于评估半导体、生物制药、医疗、实验室及科研院所、新能源等领域的洁净室、无尘室或者无菌室等环境。         一般来说,晶圆光刻、制造、测试等级为100级或1000级的洁净间,百级洁净间要求空气中0.5微米的尘埃粒子数不得超过每立方米3520个;等级为1000级的洁净间要求0.5微米的尘埃粒子数不得超过每立方米35200个。         晶圆切割或封装工序一