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

目标

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

思路

给定一个数组 nums,判断能否将其划分为 k 个非空子集,要求每个子集的和都相等。

与数组中元素顺序无关可以排序。数组元素的和是可以枚举的,它一定大于等于数组中的最大元素。和确定了之后就可以从后向前判断能否组成这个和,如果不能则立即返回。

// todo

代码

性能