题目描述

Partition to K Equal Sum Subsets

给定一个正整数的数组nums, 以及一个整数K，返回一个布尔值，确定是否可以将 nums划分为 K个和相等的子集 示例1：

Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
Output: True
Explanation: 可以分为4个子集分别为 (5), (1, 4), (2,3), (2,3) 和均为5.

另满足：

• 1 <= k <= len(nums) <= 16
• 0 < nums[i] < 10000

From leetcode No.698 Medium (opens new window)

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var canPartitionKSubsets = function(nums, k) {
    
};

解法

点击查看

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var canPartitionKSubsets = function (nums, k) {
  if (nums.length === 0) //特殊情况
    return true
  const sum = nums.reduce((x, y) => x + y, 0)
  if (sum % k !== 0) //判断是否能整除
    return false
  const sub = sum / k
  let n = Array.from(nums).sort((a, b) => a - b) //新数组从小到大排序
  if (n[n.length - 1] > sub){ //最大值超过平均值
    return false
  }else{
    while (n[n.length - 1] === sub) { //过滤掉值为平均值的元素
      n.pop()
      k--;
    }
    if (n.length === 0)
      return true
  }

  const groups = new Array(k).fill(0) //分组

  return search(groups)

  function search(groups) {
    if (n.length === 0) { //出口，所有元素分配完成
      if (groups[k - 1] === sub) //最后一组也符合条件，表示分配成功
        return true
      return false
    }
    const num = n.pop()
    for (let i = 0; i < k; i++) {
      if (groups[i] + num <= sub) {
        groups[i] += num
        if (search(groups))
          return true
        groups[i] -= num
      }
    }
    n.push(num)
    return false
  }
};

总结

如果返回值为 true，则每部分和均为 subsum = sum(nums) / k
优化项：

• 如果 nums中的元素最大值超过 subsum则直接返回 false
• 将 nums排序，方便获取到最大值，同时方便遍历

难点：

• 如何将排序后的 nums分为符合要求的 k部分

思路：

• 一次分配不成立，不代表最终结果不成立，因为还存在多种分配方式
• 一个元素被分到一个组后，先深度优先，验证后续结果，如果符合要求，则直接返回true。
• 如果不成立，则考虑把它分到后续的组，即排列组合所有情况，整体思路是穷举法
• 如何分配一个元素后即得到它最终的结果：用到递归
• 递归的出口：
  • 每次分配一个元素后，最后的结果为 true，则返回 true
  • 分配完所有元素后，仍没有返回 true，返回 false