0698. Partition to K Equal Sum Subsets¶
题目信息¶
- 题号:
0698
- 难度:
Medium
- 主题:
正整数数组、k 个非空子集、等和划分、全部元素使用
- 原题:
- 重点:
每个数组位置恰好分配一次、必须得到恰好 k 个非空子集、所有子集元素和相同、子集内部顺序无关
题目重述¶
给定正整数数组 nums 和整数 k,判断能否把数组中的全部元素划分为恰好 k 个非空子集,使每个子集的元素和都相等。
每个数组位置必须恰好属于一个子集,不能遗漏或重复使用元素;相同数值位于不同位置时是不同元素。子集不要求连续,子集之间以及子集内部的顺序都没有意义。nums.length 位于 [1, 16],元素位于 [1, 10^4],k 位于 [1, nums.length]。
自建示例¶
能够组成三组相同总和:
输入:nums = [1,1,2,2,3,3],k = 3
输出:true
解释:可以划分为 [1,3]、[1,3] 和 [2,2],三个子集的元素和都为 4。
数组总和无法平均分配:
输入:nums = [1,2,3,5],k = 2
输出:false
解释:数组总和为 11,不能分成两个整数和相同的子集。