2023-09-13：用go語言，給定一個整數(shù)數(shù)組 nums 和一個正整數(shù) k，

找出是否有可能把這個數(shù)組分成 k 個非空子集，其總和都相等。

輸入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4。

輸出： True。

來自左程云。

答案2023-09-13：

第一種算法（canPartitionKSubsets1）使用動態(tài)規(guī)劃的思想，具體過程如下：

1.計算數(shù)組nums的總和sum。如果sum不能被k整除，則直接返回false。

2.調(diào)用process1函數(shù)，傳入數(shù)組nums、status初始值為0、sum初始值為0、sets初始值為0、limit為sum/k、k和一個空的dp map。

3.在process1函數(shù)中，首先檢查dp map，如果已經(jīng)計算過該狀態(tài)，則直接返回dp[status]。

4.如果sets等于k，表示已經(jīng)找到k個非空子集，返回1。

5.遍歷數(shù)組nums，對于每個數(shù)字nums[i]，判斷該數(shù)字是否可以加入到當(dāng)前的子集中。

6.如果當(dāng)前子集的和加上nums[i]等于limit，則將狀態(tài)status的第i位設(shè)置為1，sum重置為0，sets加1，繼續(xù)遞歸調(diào)用process1函數(shù)。

7.如果當(dāng)前子集的和加上nums[i]小于limit，則將狀態(tài)status的第i位設(shè)置為1，sum加上nums[i]，sets保持不變，繼續(xù)遞歸調(diào)用process1函數(shù)。

8.如果遞歸調(diào)用的結(jié)果為1，則表示找到了滿足條件的分組，設(shè)置ans為1，并跳出循環(huán)。

9.更新dp map，將狀態(tài)status對應(yīng)的結(jié)果ans存入dp[status]，并返回ans。

第二種算法（canPartitionKSubsets2）使用回溯的思想，具體過程如下：

1.計算數(shù)組nums的總和sum。如果sum不能被k整除，則直接返回false。

2.將數(shù)組nums按照從大到小的順序排序。

3.創(chuàng)建一個長度為k的數(shù)組group，用于存放k個子集的和，初始值都為0。

4.調(diào)用partitionK函數(shù)，傳入group、sum/k、排序后的nums數(shù)組和nums數(shù)組的長度-1。

5.在partitionK函數(shù)中，如果index小于0，表示已經(jīng)遍歷完了數(shù)組nums，此時返回true。

6.取出nums[index]作為當(dāng)前要放入子集的數(shù)字。

7.遍歷group數(shù)組，對于group數(shù)組中的每個元素group[i]，如果將當(dāng)前數(shù)字nums[index]放入到group[i]中不超過目標(biāo)和target，則將該數(shù)字放入group[i]。

8.遞歸調(diào)用partitionK函數(shù)，傳入更新過的group、target、nums和index-1。

9.如果遞歸調(diào)用的結(jié)果為true，則表示找到了滿足條件的分組，返回true。

10.從i+1開始，減少重復(fù)計算，跳過和group[i]相等的元素。

11.返回false。

第一種算法的時間復(fù)雜度為O(k * 2^n)，其中n是數(shù)組nums的長度，對于每個狀態(tài)，需要遍歷一次nums數(shù)組。

第二種算法的時間復(fù)雜度為O(k * n * 2^n)，其中n是數(shù)組nums的長度，對于每個狀態(tài)，需要遍歷一次group數(shù)組和nums數(shù)組。

第一種算法的額外空間復(fù)雜度為O(2^n)，用于存儲dp map。

第二種算法的額外空間復(fù)雜度為O(k)，用于存儲group數(shù)組。

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