2023-09-13：用go语言，给定一个整数数组 nums 和一个正整数 k， 找出是否有可能把这个数组分成 k 个非空子集，

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完整代码如下：

在这里插入图片描述rust完整代码如下：

在这里插入图片描述c++完整代码如下：

在这里插入图片描述c完整代码如下：

在这里插入图片描述