// 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)
将整数数组分割为 k 个子数组, 和相等 -- 698
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 给出一个整数数字，有正有负，找一个长度大于等于k的一个子数组（即数组中相邻的k个数），使他的平均值最大。示例：给出...
- public class test{ public static void main(String[] args)...
- 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的...
