class Solution {
public:
bool canPartitionKSubsets(vector<int>& nums, int 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) <= 160 < nums[i] < 10000[1,4] 范围内相似题目
原站题解
php 解法, 执行用时: 152 ms, 内存消耗: 21 MB, 提交时间: 2021-06-02 15:12:47
class Solution {
/**
* @param Integer[] $nums
* @param Integer $k
* @return Boolean
*/
function canPartitionKSubsets($nums, $k) {
$sum = array_sum($nums);
if ( $sum % $k != 0 ) return false;
$target = $sum / $k;
if ( max($nums) > $target ) return false;
sort($nums);
$n = count($nums);
$size = 1 << $n;
$dp = array_fill(0, $size, false);
$dp[0] = true;
$curSum = array_fill(0, $size, 0);
for ( $i = 0; $i < $size; $i++ ) {
if ( !$dp[$i] ) continue;
for ( $j = 0; $j < $n; $j++ ) {
if ( ($i & (1 << $j)) != 0 ) continue;
$next = $i | (1 << $j);
if ( $dp[$next] ) continue;
if ( $curSum[$i] % $target + $nums[$j] <= $target ) {
$curSum[$next] = $curSum[$i] + $nums[$j];
$dp[$next] = true;
} else {
break;
}
}
}
return $dp[$size-1];
}
}