2023-09-13：用 go 语言，给定一个整数数组 nums 和一个正整数 k，
找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4。
输出： True。
来自左程云。
答案 2023-09-13：
第一种算法（canPartitionKSubsets1）使用动态规划的思想，具体过程如下：
1.计算数组 nums 的总和 sum。如果 sum 不能被 k 整除，则直接返回 false。
2.调用 process1 函数，传入数组 nums、status 初始值为 0、sum 初始值为 0、sets 初始值为 0、limit 为 sum/k、k 和一个空的 dp map。
3.在 process1 函数中，首先检查 dp map，如果已经计算过该状态，则直接返回 dp[status]。
4.如果 sets 等于 k，表示已经找到 k 个非空子集，返回 1。
5.遍历数组 nums，对于每个数字 nums[i]，判断该数字是否可以加入到当前的子集中。
6.如果当前子集的和加上 nums[i]等于 limit，则将状态 status 的第 i 位设置为 1，sum 重置为 0，sets 加 1，继续递归调用 process1 函数。
7.如果当前子集的和加上 nums[i]小于 limit，则将状态 status 的第 i 位设置为 1，sum 加上 nums[i]，sets 保持不变，继续递归调用 process1 函数。
8.如果递归调用的结果为 1，则表示找到了满足条件的分组，设置 ans 为 1，并跳出循环。
9.更新 dp map，将状态 status 对应的结果 ans 存入 dp[status]，并返回 ans。
第二种算法（canPartitionKSubsets2）使用回溯的思想，具体过程如下：
1.计算数组 nums 的总和 sum。如果 sum 不能被 k 整除，则直接返回 false。
2.将数组 nums 按照从大到小的顺序排序。
3.创建一个长度为 k 的数组 group，用于存放 k 个子集的和，初始值都为 0。
4.调用 partitionK 函数，传入 group、sum/k、排序后的 nums 数组和 nums 数组的长度-1。
5.在 partitionK 函数中，如果 index 小于 0，表示已经遍历完了数组 nums，此时返回 true。
6.取出 nums[index]作为当前要放入子集的数字。
7.遍历 group 数组，对于 group 数组中的每个元素 group[i]，如果将当前数字 nums[index]放入到 group[i]中不超过目标和 target，则将该数字放入 group[i]。
8.递归调用 partitionK 函数，传入更新过的 group、target、nums 和 index-1。
9.如果递归调用的结果为 true，则表示找到了满足条件的分组，返回 true。
10.从 i+1 开始，减少重复计算，跳过和 group[i]相等的元素。
11.返回 false。
第一种算法的时间复杂度为 O(k * 2^n)，其中 n 是数组 nums 的长度，对于每个状态，需要遍历一次 nums 数组。
第二种算法的时间复杂度为 O(k * n * 2^n)，其中 n 是数组 nums 的长度，对于每个状态，需要遍历一次 group 数组和 nums 数组。
第一种算法的额外空间复杂度为 O(2^n)，用于存储 dp map。
第二种算法的额外空间复杂度为 O(k)，用于存储 group 数组。
go 完整代码如下：
package main
import ( "fmt" "sort")
func canPartitionKSubsets1(nums []int, k int) bool { sum := 0 for _, num := range nums { sum += num } if sum%k != 0 { return false } return process1(nums, 0, 0, 0, sum/k, k, make(map[int]int)) == 1}
func process1(nums []int, status, sum, sets, limit, k int, dp map[int]int) int { if ans, ok := dp[status]; ok { return ans } ans := -1 if sets == k { ans = 1 } else { for i := 0; i < len(nums); i++ { if (status&(1<<i)) == 0 && sum+nums[i] <= limit { if sum+nums[i] == limit { ans = process1(nums, status|(1<<i), 0, sets+1, limit, k, dp) } else { ans = process1(nums, status|(1<<i), sum+nums[i], sets, limit, k, dp) }
if ans == 1 { break } } } } dp[status] = ans return ans}
func canPartitionKSubsets2(nums []int, k int) bool { sum := 0 for _, num := range nums { sum += num } if sum%k != 0 { return false } sort.Ints(nums) return partitionK(make([]int, k), sum/k, nums, len(nums)-1)}
func partitionK(group []int, target int, nums []int, index int) bool { if index < 0 { return true }
num := nums[index] len := len(group) for i := 0; i < len; i++ { if group[i]+num <= target { group[i] += num if partitionK(group, target, nums, index-1) { return true } group[i] -= num for i+1 < len && group[i] == group[i+1] { i++ } } } return false}
func main() { nums := []int{4, 3, 2, 3, 5, 2, 1} k := 4 fmt.Println(canPartitionKSubsets1(nums, k)) fmt.Println(canPartitionKSubsets2(nums, k))}
复制代码
rust 完整代码如下：
fn can_partition_k_subsets1(nums: Vec<i32>, k: i32) -> bool { let sum: i32 = nums.iter().sum(); if sum % k != 0 { return false; } let mut dp: Vec<i32> = vec![0; 1 << nums.len()]; process1(nums, 0, 0, 0, sum / k, k, &mut dp) == 1}
fn process1( nums: Vec<i32>, status: usize, sum: i32, sets: i32, limit: i32, k: i32, dp: &mut Vec<i32>,) -> i32 { if dp[status] != 0 { return dp[status]; } let mut ans = -1; if sets == k { ans = 1; } else { for i in 0..nums.len() { if (status & (1 << i)) == 0 && sum + nums[i] <= limit { if sum + nums[i] == limit { ans = process1(nums.clone(), status | (1 << i), 0, sets + 1, limit, k, dp); } else { ans = process1( nums.clone(), status | (1 << i), sum + nums[i], sets, limit, k, dp, ); } if ans == 1 { break; } } } } dp[status] = ans; return ans;}
fn can_partition_k_subsets2(nums: Vec<i32>, k: i32) -> bool { let sum: i32 = nums.iter().sum(); if sum % k != 0 { return false; } let mut sorted_nums = nums.clone(); sorted_nums.sort(); partition_k( &mut vec![0; k as usize], sum / k, &sorted_nums, (sorted_nums.len() - 1) as i32, )}
fn partition_k(group: &mut Vec<i32>, target: i32, nums: &Vec<i32>, index: i32) -> bool { if index < 0 { return true; } let num = nums[index as usize]; let len = group.len() as i32; for mut i in 0..len { if group[i as usize] + num <= target { group[i as usize] += num; if partition_k(group, target, nums, index - 1) { return true; } group[i as usize] -= num; while i + 1 < group.len() as i32 && group[i as usize] == group[(i + 1) as usize] { i += 1; } } } false}
fn main() { let nums = vec![4, 3, 2, 3, 5, 2, 1]; let k = 4; let result1 = can_partition_k_subsets1(nums.clone(), k); let result2 = can_partition_k_subsets2(nums.clone(), k); println!("Result using can_partition_k_subsets1: {}", result1); println!("Result using can_partition_k_subsets2: {}", result2);}
复制代码
c++完整代码如下：
#include <iostream>#include <vector>#include <algorithm>
using namespace std;
bool process1(vector<int>& nums, int status, int sum, int sets, int limit, int k, vector<int>& dp) { if (dp[status] != 0) { return dp[status] == 1; } bool ans = false; if (sets == k) { ans = true; } else { for (int i = 0; i < nums.size(); i++) { if ((status & (1 << i)) == 0 && sum + nums[i] <= limit) { if (sum + nums[i] == limit) { ans = process1(nums, status | (1 << i), 0, sets + 1, limit, k, dp); } else { ans = process1(nums, status | (1 << i), sum + nums[i], sets, limit, k, dp); } if (ans) { break; } } } } dp[status] = ans ? 1 : -1; return ans;}
bool canPartitionKSubsets1(vector<int>& nums, int k) { int sum = 0; for (int num : nums) { sum += num; } if (sum % k != 0) { return false; } vector<int> dp(1 << nums.size(), 0); return process1(nums, 0, 0, 0, sum / k, k, dp);}
bool partitionK(vector<int>& group, int target, vector<int>& nums, int index) { if (index < 0) { return true; } int num = nums[index]; int len = group.size(); for (int i = 0; i < len; i++) { if (group[i] + num <= target) { group[i] += num; if (partitionK(group, target, nums, index - 1)) { return true; } group[i] -= num; while (i + 1 < group.size() && group[i] == group[i + 1]) { i++; } } } return false;}
bool canPartitionKSubsets2(vector<int>& nums, int k) { int sum = 0; for (int num : nums) { sum += num; } if (sum % k != 0) { return false; } sort(nums.begin(), nums.end()); vector<int> t = vector<int>(k, 0); return partitionK(t, sum / k, nums, nums.size() - 1);}
int main(){ vector<int> nums = { 4, 3, 2, 3, 5, 2, 1 }; int k = 4;
bool result1 = canPartitionKSubsets1(nums, k); cout << "Result using canPartitionKSubsets1: " << (result1 ? "true" : "false") << endl;
bool result2 = canPartitionKSubsets2(nums, k); cout << "Result using canPartitionKSubsets2: " << (result2 ? "true" : "false") << endl;
return 0;}
复制代码
c 完整代码如下：
#include <stdio.h>#include <stdbool.h>#include <stdlib.h>
int process1(int* nums, int numsSize, int status, int sum, int sets, int limit, int k, int* dp) { if (dp[status] != 0) { return dp[status]; } int ans = -1; if (sets == k) { ans = 1; } else { for (int i = 0; i < numsSize; i++) { if ((status & (1 << i)) == 0 && sum + nums[i] <= limit) { if (sum + nums[i] == limit) { ans = process1(nums, numsSize, status | (1 << i), 0, sets + 1, limit, k, dp); } else { ans = process1(nums, numsSize, status | (1 << i), sum + nums[i], sets, limit, k, dp); } if (ans == 1) { break; } } } } dp[status] = ans; return ans;}
bool canPartitionKSubsets1(int* nums, int numsSize, int k) { int sum = 0; for (int i = 0; i < numsSize; i++) { sum += nums[i]; } if (sum % k != 0) { return false; } int* dp = (int*)malloc((1 << numsSize) * sizeof(int)); for (int i = 0; i < (1 << numsSize); i++) { dp[i] = 0; } bool result = process1(nums, numsSize, 0, 0, 0, sum / k, k, dp) == 1; free(dp); return result;}
bool partitionK(int* group, int target, int* nums, int index, int len) { if (index < 0) { return true; } int num = nums[index]; for (int i = 0; i < len; i++) { if (group[i] + num <= target) { group[i] += num; if (partitionK(group, target, nums, index - 1, len)) { return true; } group[i] -= num; while (i + 1 < len && group[i] == group[i + 1]) { i++; } } } return false;}
bool canPartitionKSubsets2(int* nums, int numsSize, int k) { int sum = 0; for (int i = 0; i < numsSize; i++) { sum += nums[i]; } if (sum % k != 0) { return false; } for (int i = 0; i < numsSize; i++) { for (int j = i + 1; j < numsSize; j++) { if (nums[i] < nums[j]) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } } } int target = sum / k; int* group = (int*)malloc(k * sizeof(int)); for (int i = 0; i < k; i++) { group[i] = 0; } bool result = partitionK(group, target, nums, numsSize - 1, k); free(group); return result;}
int main() { int nums[] = { 4, 3, 2, 3, 5, 2, 1 }; int numsSize = sizeof(nums) / sizeof(nums[0]); int k = 4;
bool result1 = canPartitionKSubsets1(nums, numsSize, k); bool result2 = canPartitionKSubsets2(nums, numsSize, k);
printf("Result from canPartitionKSubsets1: %s\n", result1 ? "true" : "false"); printf("Result from canPartitionKSubsets2: %s\n", result2 ? "true" : "false");
return 0;}
复制代码
评论