[路飞]_698. 划分为k个相等的子集

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] 范围内

题解

递归 + 回溯

假设：

• 数组长度为 len
• 数组总和为 total

那么：

• 数组元素总和一定可以被 $k$ 整除，否者直接返回 $false$
• 如果可以平分，每个非空子集的总和 $target = total/k$
• 创建长度为 $k$ 的桶,桶的初始值设置为 $0$
• 递归

递归

数组从左到右枚举，优先将第一个桶装满到 $target$ ,如果枚举整个数组都不能将桶$0$正好装满$target$;可以结束递归了，因为第一个桶都不能满足 $target$ ；再装以后的桶毫无意义

枚举数组如果可以将桶0装满，继续装填桶1，直到将桶k也装满；返回true

根据上述思路编辑代码如下：

var canPartitionKSubsets = function (nums, k) {
  const total = nums.reduce((a, b) => a + b)
  if (total % k !== 0) return false
  const target = total / k
  const list = Array(k).fill(0)
  const len = nums.length
  return dfs(0)
  function dfs(index) {
    if (index === len) return true
    for (let i = 0; i < k; i++) {
      if (list[i] + nums[index] <= target) {
        list[i] += nums[index]
        if (dfs(index + 1)) return true
        list[i] -= nums[index]
      }
      if (list[i] === 0 || list[i] + nums[index] === target) break
    }
    return false
  }
}
复制代码

结语

作者水平有限，如有不足欢迎指正；任何意见和建议欢迎评论区浏览讨论