递归回溯法，回顾求和与 reduce / array_reduce / Aggregate / accumulate 使用，求解《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] 范围内
答案
递归 · 回溯法
var canPartitionKSubsets = function(nums, k) {
const totalSum = _.sum(nums)
if (totalSum % k !== 0) return false
const subSum = totalSum / k, n = nums.length, sums = new Uint16Array(k)
nums.sort((a, b) => b - a)
return (function d(i) {
if (i === n) return true
for (let j = 0; j < k; j++) {
if (j > 0 && sums[j] === sums[j - 1]) continue
if (sums[j] + nums[i] > subSum) continue
sums[j] += nums[i]
if (d(i + 1)) return true
sums[j] -= nums[i]
}
return false
})(0)
};function canPartitionKSubsets(nums: number[], k: number): boolean {
const totalSum = nums.reduce((p: number, v: number) => p + v)
if (totalSum % k > 0) return false
const subSum = totalSum / k, n = nums.length, sums = new Uint16Array(k)
nums.sort((a, b) => b - a)
return (function d(i: number): boolean {
if (i === n) return true
for (let j = 0; j < k; j++) {
if (j > 0 && sums[j] === sums[j - 1]) continue
if (sums[j] + nums[i] > subSum) continue
sums[j] += nums[i]
if (d(i + 1)) return true
sums[j] -= nums[i]
}
return false
})(0)
};class Solution {
function canPartitionKSubsets($nums, $k) {
$totalSum = array_sum($nums);
if ($totalSum % $k > 0) return false;
rsort($nums);
return $this->d(0, count($nums), $totalSum / $k, $k, $nums, array_fill(0, $k, 0));
}
function d($i, $n, $subSum, $k, &$nums, &$sums) {
if ($i === $n) return true;
for ($j = 0; $j < $k; $j++) {
if ($j > 0 && $sums[$j] === $sums[$j - 1]) continue;
if ($sums[$j] + $nums[$i] > $subSum) continue;
$sums[$j] += $nums[$i];
if ($this->d($i + 1, $n, $subSum, $k, $nums, $sums)) return true;
$sums[$j] -= $nums[$i];
}
return false;
}
}func canPartitionKSubsets(nums []int, k int) bool {
totalSum := 0
for _, num := range nums {
totalSum += num
}
if totalSum % k > 0 {
return false
}
subSum, n, sums := totalSum / k, len(nums), make([]int, k)
sort.Sort(sort.Reverse(sort.IntSlice(nums)))
var d func(i int) bool
d = func(i int) bool {
if i == n {
return true
}
for j := 0; j < k; j++ {
if j > 0 && sums[j] == sums[j - 1] {
continue
}
if sums[j] + nums[i] > subSum {
continue
}
sums[j] += nums[i]
if d(i + 1) {
return true
}
sums[j] -= nums[i]
}
return false
}
return d(0)
}class Solution {
int[] sums;
public boolean canPartitionKSubsets(int[] nums, int k) {
int totalSum = Arrays.stream(nums).sum();
if (totalSum % k > 0) return false;
int n = nums.length;
sums = new int[k];
Arrays.sort(nums);
for (int i = 0, j = n - 1; i < j; i++, j--) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
return d(0, n, k, totalSum / k, nums);
}
public boolean d(int i, int n, int k, int subSum, int[] nums) {
if (i == n) return true;
for (int j = 0; j < k; j++) {
if (j > 0 && sums[j] == sums[j - 1]) continue;
if (sums[j] + nums[i] > subSum) continue;
sums[j] += nums[i];
if (d(i + 1, n, k, subSum, nums)) return true;
sums[j] -= nums[i];
}
return false;
}
}public class Solution {
int[] sums;
public bool CanPartitionKSubsets(int[] nums, int k) {
int totalSum = nums.Sum();
if (totalSum % k > 0) return false;
int n = nums.Length;
sums = new int[k];
Array.Sort(nums, (a, b) => b - a);
return d(0, n, k, totalSum / k, nums);
}
public bool d(int i, int n, int k, int subSum, int[] nums) {
if (i == n) return true;
for (int j = 0; j < k; j++) {
if (j > 0 && sums[j] == sums[j - 1]) continue;
if (sums[j] + nums[i] > subSum) continue;
sums[j] += nums[i];
if (d(i + 1, n, k, subSum, nums)) return true;
sums[j] -= nums[i];
}
return false;
}
}static inline int cmp(const void *pa, const void *pb) {
return *(int*)pb - *(int*)pa;
}
bool d(int i, int numsSize, int k, int subSum, int* nums, int* sums) {
if (i == numsSize) return true;
for (int j = 0; j < k; j++) {
if (j > 0 && sums[j] == sums[j - 1]) continue;
if (sums[j] + nums[i] > subSum) continue;
sums[j] += nums[i];
if (d(i + 1, numsSize, k, subSum, nums, sums)) return true;
sums[j] -= nums[i];
}
return false;
}
bool canPartitionKSubsets(int* nums, int numsSize, int k){
int totalSum = 0;
for (int i = 0; i < numsSize; i++) totalSum += nums[i];
if (totalSum % k > 0) return false;
qsort(nums, numsSize, sizeof(int), cmp);
int* sums = malloc(sizeof(int) * k);
memset(sums, 0, sizeof(int) * k);
return d(0, numsSize, k, totalSum / k, nums, sums);
}class Solution {
public:
bool canPartitionKSubsets(vector<int>& nums, int k) {
int totalSum = accumulate(nums.begin(), nums.end(), 0);
if (totalSum % k > 0) return false;
sort(nums.begin(), nums.end(), greater<int>());
vector<int> sums(k, 0);
auto d = [&, n = nums.size(), subSum = totalSum / k] (auto& d, int i) {
if (i == n) return true;
for (int j = 0; j < k; j++) {
if (j > 0 && sums[j] == sums[j - 1]) continue;
if (sums[j] + nums[i] > subSum) continue;
sums[j] += nums[i];
if (d(d, i + 1)) return true;
sums[j] -= nums[i];
}
return false;
};
return d(d, 0);
}
};class Solution:
def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
totalSum = sum(nums)
if totalSum % k > 0: return False
nums.sort(key = lambda v : -v)
n, subSum, sums = len(nums), totalSum / k, [0] * k
def d(i: int) -> bool:
nonlocal n, subSum, sums, nums
if i == n: return True
for j in range(0, k):
if j > 0 and sums[j - 1] == sums[j]: continue
if sums[j] + nums[i] > subSum: continue
sums[j] += nums[i]
if d(i + 1): return True
sums[j] -= nums[i]
return False
return d(0)递归 · 回溯法 · 回顾 reduce 使用
var canPartitionKSubsets = function(nums, k) {
const totalSum = _.sum(nums)
if (totalSum % k !== 0) return false
const subSum = totalSum / k, n = nums.length, sums = new Uint16Array(k)
nums.sort((a, b) => b - a)
return (function d(i) {
if (i === n) return sums.every(sum => sum === subSum)
for (let j = 0; j < k; j++) {
if (j > 0 && sums[j] === sums[j - 1]) continue
if (sums[j] + nums[i] > subSum) continue
sums[j] += nums[i]
if (d(i + 1)) return true
sums[j] -= nums[i]
}
return false
})(0)
};function canPartitionKSubsets(nums: number[], k: number): boolean {
const totalSum = nums.reduce((p: number, v: number) => p + v)
if (totalSum % k > 0) return false
const subSum = totalSum / k, n = nums.length, sums = new Uint16Array(k)
nums.sort((a, b) => b - a)
return (function d(i: number): boolean {
if (i === n) return sums.every(sum => sum === subSum)
for (let j = 0; j < k; j++) {
if (j > 0 && sums[j] === sums[j - 1]) continue
if (sums[j] + nums[i] > subSum) continue
sums[j] += nums[i]
if (d(i + 1)) return true
sums[j] -= nums[i]
}
return false
})(0)
};class Solution {
function canPartitionKSubsets($nums, $k) {
$totalSum = array_sum($nums);
if ($totalSum % $k > 0) return false;
rsort($nums);
return $this->d(0, count($nums), $totalSum / $k, $k, $nums, array_fill(0, $k, 0));
}
function d($i, $n, $subSum, $k, &$nums, &$sums) {
if ($i === $n) return array_reduce($sums, fn($isTrue, $sum) => $isTrue && $sum === $subSum, true);
for ($j = 0; $j < $k; $j++) {
if ($j > 0 && $sums[$j] === $sums[$j - 1]) continue;
if ($sums[$j] + $nums[$i] > $subSum) continue;
$sums[$j] += $nums[$i];
if ($this->d($i + 1, $n, $subSum, $k, $nums, $sums)) return true;
$sums[$j] -= $nums[$i];
}
return false;
}
}func canPartitionKSubsets(nums []int, k int) bool {
totalSum := 0
for _, num := range nums {
totalSum += num
}
if totalSum % k > 0 {
return false
}
subSum, n, sums := totalSum / k, len(nums), make([]int, k)
sort.Sort(sort.Reverse(sort.IntSlice(nums)))
var d func(i int) bool
d = func(i int) bool {
if i == n {
for _, sum := range sums {
if sum != subSum {
return false
}
}
return true
}
for j := 0; j < k; j++ {
if j > 0 && sums[j] == sums[j - 1] {
continue
}
if sums[j] + nums[i] > subSum {
continue
}
sums[j] += nums[i]
if d(i + 1) {
return true
}
sums[j] -= nums[i]
}
return false
}
return d(0)
}class Solution {
int[] sums;
public boolean canPartitionKSubsets(int[] nums, int k) {
int totalSum = Arrays.stream(nums).sum();
if (totalSum % k > 0) return false;
int n = nums.length;
sums = new int[k];
Arrays.sort(nums);
for (int i = 0, j = n - 1; i < j; i++, j--) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
return d(0, n, k, totalSum / k, nums);
}
public boolean d(int i, int n, int k, int subSum, int[] nums) {
if (i == n) return Arrays.stream(sums).reduce(1, (isTrue, sum) -> isTrue == 1 && sum == subSum ? 1 : 0) == 1;
for (int j = 0; j < k; j++) {
if (j > 0 && sums[j] == sums[j - 1]) continue;
if (sums[j] + nums[i] > subSum) continue;
sums[j] += nums[i];
if (d(i + 1, n, k, subSum, nums)) return true;
sums[j] -= nums[i];
}
return false;
}
}class Solution {
int[] sums;
public boolean canPartitionKSubsets(int[] nums, int k) {
int totalSum = Arrays.stream(nums).sum();
if (totalSum % k > 0) return false;
sums = new int[k];
Integer[] ns = Arrays.stream(nums).boxed().toArray(Integer[]::new);
Arrays.sort(ns, (a, b)-> b - a);
nums = Arrays.stream(ns).mapToInt(v -> v).toArray();
return d(0, nums.length, k, totalSum / k, nums);
}
public boolean d(int i, int n, int k, int subSum, int[] nums) {
if (i == n) return Arrays.stream(sums).reduce(1, (isTrue, sum) -> isTrue == 1 && sum == subSum ? 1 : 0) == 1;
for (int j = 0; j < k; j++) {
if (j > 0 && sums[j] == sums[j - 1]) continue;
if (sums[j] + nums[i] > subSum) continue;
sums[j] += nums[i];
if (d(i + 1, n, k, subSum, nums)) return true;
sums[j] -= nums[i];
}
return false;
}
}public class Solution {
int[] sums;
public bool CanPartitionKSubsets(int[] nums, int k) {
int totalSum = nums.Sum();
if (totalSum % k > 0) return false;
int n = nums.Length;
sums = new int[k];
Array.Sort(nums, (a, b) => b - a);
return d(0, n, k, totalSum / k, nums);
}
public bool d(int i, int n, int k, int subSum, int[] nums) {
if (i == n) return sums.Aggregate(true, (isTrue, sum) => isTrue && sum == subSum);
for (int j = 0; j < k; j++) {
if (j > 0 && sums[j] == sums[j - 1]) continue;
if (sums[j] + nums[i] > subSum) continue;
sums[j] += nums[i];
if (d(i + 1, n, k, subSum, nums)) return true;
sums[j] -= nums[i];
}
return false;
}
}static inline int cmp(const void *pa, const void *pb) {
return *(int*)pb - *(int*)pa;
}
bool d(int i, int numsSize, int k, int subSum, int* nums, int* sums) {
if (i == numsSize) {
for (int j = 0; j < k; j++) if (sums[j] != subSum) return false;
return true;
}
for (int j = 0; j < k; j++) {
if (j > 0 && sums[j] == sums[j - 1]) continue;
if (sums[j] + nums[i] > subSum) continue;
sums[j] += nums[i];
if (d(i + 1, numsSize, k, subSum, nums, sums)) return true;
sums[j] -= nums[i];
}
return false;
}
bool canPartitionKSubsets(int* nums, int numsSize, int k){
int totalSum = 0;
for (int i = 0; i < numsSize; i++) totalSum += nums[i];
if (totalSum % k > 0) return false;
qsort(nums, numsSize, sizeof(int), cmp);
int* sums = malloc(sizeof(int) * k);
memset(sums, 0, sizeof(int) * k);
return d(0, numsSize, k, totalSum / k, nums, sums);
}class Solution {
public:
bool canPartitionKSubsets(vector<int>& nums, int k) {
int totalSum = accumulate(nums.begin(), nums.end(), 0);
if (totalSum % k > 0) return false;
sort(nums.begin(), nums.end(), greater<int>());
vector<int> sums(k, 0);
auto d = [&, n = nums.size(), subSum = totalSum / k] (auto& d, int i) {
if (i == n) return accumulate(sums.begin(), sums.end(), true, [&](bool isTrue, int sum) -> bool {
return isTrue && sum == subSum;
});
for (int j = 0; j < k; j++) {
if (j > 0 && sums[j] == sums[j - 1]) continue;
if (sums[j] + nums[i] > subSum) continue;
sums[j] += nums[i];
if (d(d, i + 1)) return true;
sums[j] -= nums[i];
}
return false;
};
return d(d, 0);
}
};class Solution:
def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:
totalSum = sum(nums)
if totalSum % k > 0: return False
nums.sort(key = lambda v : -v)
n, subSum, sums = len(nums), totalSum / k, [0] * k
def d(i: int) -> bool:
nonlocal n, subSum, sums, nums
if i == n: return reduce(lambda isTrue, sum: isTrue and sum == subSum, sums, True)
for j in range(0, k):
if j > 0 and sums[j - 1] == sums[j]: continue
if sums[j] + nums[i] > subSum: continue
sums[j] += nums[i]
if d(i + 1): return True
sums[j] -= nums[i]
return False
return d(0)