【2022-09-20每日一题】698. 划分为k个相等的子集
2022-09-20
2分钟阅读时长
2022-09-20每日一题：698. 划分为k个相等的子集
难度：Medium
标签：位运算 、 记忆化搜索 、 数组 、 动态规划 、 回溯 、 状态压缩
给定一个整数数组 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) <= 160 < nums[i] < 10000- 每个元素的频率在
[1,4]范围内
方法一：状态压缩 + 记忆化搜索
详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读
func canPartitionKSubsets(nums []int, k int) bool {
all := 0
for _, num := range nums {
all += num
}
// 不能整除
if all%k > 0 {
return false
}
sort.Ints(nums)
n, avg := len(nums), all/k
if nums[n-1] > avg {
return false
}
dp := make([]bool, 1 << n)
var dfs func(int, int) bool
dfs = func (s, p int) bool {
if s == 0 { // 所有数字都选择了，表示原始数组可以按照题目要求来进行分配
return true
}
if dp[s] { // 剪枝
return false
}
dp[s] = true
for i, num := range nums {
if num+p > avg { // 累加当前数与平均数比较，大于说明不可行，直接终止
break
}
// 选择当前数，进入下一层
if s>>i&1 >0 && dfs(s^1<<i, (p+num)%avg) {
return true
}
}
return false
}
return dfs(1<<n-1, 0)
}
复杂度分析
- 时间复杂度：O(n×2^n)，其中 n 为数组 nums 的长度，共有 2^n个状态，每一个状态进行了 n 次尝试。
- 空间复杂度：O(2^n)，其中 nn 为数组 nums 的长度，主要为状态数组的空间开销。
方法二：状态压缩 + 动态规划
详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读
func canPartitionKSubsets(nums []int, k int) bool {
all := 0
for _, num := range nums {
all += num
}
// 不能整除
if all%k > 0 {
return false
}
sort.Ints(nums)
n, avg := len(nums), all/k
if nums[n-1] > avg {
return false
}
dp, curSum := make([]bool, 1<<n), make([]int, 1<<n)
dp[0] = true //初始化
for s, v := range dp {
if !v {
continue
}
for i, num := range nums {
if (curSum[s]+num) > avg { // 选择后大于平均数
break
}
if s>>i&1==0 { // 选择当前数
next := s|1<<i
if !dp[next] { // 减少重复计算
dp[next] = true
curSum[next] = (curSum[s]+num)%avg
}
}
}
}
return dp[1<<n-1]
}
复杂度分析
- 时间复杂度：O(n×2^n)，其中 n 为数组 nums 的长度，共有 2^n个状态，每一个状态进行了 n 次尝试。
- 空间复杂度：O(2^n)，其中 nn 为数组 nums 的长度，主要为状态数组的空间开销。