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;
}
