将整数数组分割为 k 个子数组, 和相等 -- 698

// NOTE: (698)给定一个整数, nums, 和 一个正整数 k;
// 找出是否可能把这个数组分成 k 个非空子集; 其总和都相等
// 1 <= k <= len(nums) <= 16
// 0 <= nums[i] <= 10000
// input: nums = [4, 3, 2, 3, 5, 2, 1], k=4
// (5), (1,4), (3,2), (2,3)
function canPartitionKSubsets(nums, k) {
  let max = nums[0]
  let sum = 0
  for (let n of nums) {
    sum = sum + n
    if (n > max) {
      max = n
    }
  }
  if (sum % k !== 0 || sum / k < max) {
    return false
  }
  let target = sum / k;
  let used = []
  return dfs(target, nums, used, 0, k, 0)
}

function dfs(target, nums, used, sum, k, start) {
  if (k === 1) {
    return true
  }
  // 搜索到了一组
  if (sum === target) {
    return dfs(target, nums, used, 0, k - 1, 0)
  }

  for (let i = start, len = nums.length; i < len; i++) {
    let total = sum + nums[i]
    if (!used[i] && total <= target) {
      used[i] = true
      if (dfs(target, nums, used, total, k, i + 1)) {
        return true
      }
      used[i] = false
    }
  }
  return false
}

function canPartitionKSubsets2(nums, k) {
  let max = nums[0]
  let sum = 0
  for (let n of nums) {
    sum = sum + n
    if (n > max) {
      max = n
    }
  }
  if (sum % k !== 0 || sum / k < max) {
    return false
  }
  let target = sum / k;
  let used = []
  return dfs(target, nums, used, 0, k, 0)
}


const r = canPartitionKSubsets([10, 10, 10, 6, 6, 6, 7, 7, 7, 7, 7, 7], 3)
console.log(r)