leetcode-698. 划分为k个相等的子集

本文主要是介绍leetcode-698. 划分为k个相等的子集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。

示例 1：

输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
输出： True
说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。

提示：

1 <= k <= len(nums) <= 16
0 < nums[i] < 10000

解题思路

想象成有k个空位置，遍历数组，对每个数字判断当前的数字能不能放到当前的空位置里面，如果能放进去，则递归，如果不能放进去，则回溯。

因为每个数字只能用一次，并且对一个相同的空位置，对于a, b, c这种的数字，当用了a，再用b时发现不可以，考虑b的时候，不需要再考虑a了，直接考虑b后面的数字即可（这里是剪枝）。这个空位置满了，就换下个空位置，下个空位置就需要考虑全部的数字了。

在分数字的时候，其实可以优先考虑大的数，超过的部分尽早剪枝。所以可以预先对nums排个序来剪枝

时间复杂度会比较高，最坏情况下复杂度会达到$o(n\ast 2^n)$（看官解得来的，但是为啥？）

代码

class Solution:def canPartitionKSubsets(self, nums: List[int], k: int) -> bool:if sum(nums) % k != 0 or max(nums) > sum(nums) // k:return Falsetarget = sum(nums) // kvisited_indexs = [False] * len(nums)def helper(nums: list, cur_sum: int, group_index: int, begin_index: int) -> bool:if group_index == k:return Trueif cur_sum == target:return helper(nums, 0, group_index + 1, 0)if cur_sum > target:return Falsefor index in range(begin_index, len(nums)):if visited_indexs[index]:continuevisited_indexs[index] = Trueif helper(nums, cur_sum + nums[index], group_index, index + 1):return Truevisited_indexs[index] = Falsereturn Falsereturn helper(nums, 0, 0, 0)

这篇关于leetcode-698. 划分为k个相等的子集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---