-
-
Notifications
You must be signed in to change notification settings - Fork 737
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
[LeetCode] 698. Partition to K Equal Sum Subsets #698
Comments
有一种利用bit位的dp做法,感觉很不错, 只是现在这些case都很小, 体现不了它的优点, 但是其中的dp思想非常棒, 建议看一下, 补充一下这个帖子 |
求贴代码~ |
位图的代码实现了一下 感觉好像leetcode提高了test数量还是啥的 现在的几个版本代码直接跑都会超时
|
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Given an integer array
nums
and an integerk
, returntrue
if it is possible to divide this array intok
non-empty subsets whose sums are all equal.Example 1:
Example 2:
Constraints:
1 <= k <= nums.length <= 16
1 <= nums[i] <= 104
[1, 4]
.这道题给了一个数组 nums 和一个数字k,问我们该数字能不能分成k个非空子集合,使得每个子集合的和相同。给了k的范围是 [1,16],而且数组中的数字都是正数。这跟之前那道 Partition Equal Subset Sum 很类似,但是那道题只让分成两个子集合,所以问题可以转换为是否存在和为整个数组和的一半的子集合,可以用 dp 来做。但是这道题让求k个和相同的,感觉无法用 dp 来做,因为就算找出了一个,其余的也需要验证。这道题可以用递归来做,首先还是求出数组的所有数字之和 sum,首先判断 sum 是否能整除k,不能整除的话直接返回 false。然后需要一个 visited 数组来记录哪些数字已经被选中了,然后调用递归函数,目标是组k个子集合,且每个子集合之和为 target = sum/k。还需要变量 start,表示从数组的某个位置开始查找,curSum 为当前子集合之和,在递归函数中,如果 k=1,说明此时只需要组一个子集合,那么当前的就是了,直接返回 true。如果 curSum 等于 target 了,则再次调用递归,此时传入 k-1,start 和 curSum 都重置为0,因为当前又找到了一个和为 target 的子集合,要开始继续找下一个。否则的话就从 start 开始遍历数组,如果当前数字已经访问过了则直接跳过,否则标记为已访问。然后调用递归函数,k保持不变,因为还在累加当前的子集合,start 传入 i+1,curSum 传入 curSum+nums[i],因为要累加当前的数字,如果递归函数返回 true 了,则直接返回 true。否则就将当前数字重置为未访问的状态继续遍历,参见代码如下:
解法一:
我们也可以对上面的解法进行一些优化,比如先给数组按从大到小的顺序排个序,然后在递归函数中,可以直接判断,如果 curSum 大于 target 了,直接返回 false,因为题目中限定了都是正数,并且也给数组排序了,后面的数字只能更大,这个剪枝操作大大的提高了运行速度,感谢热心网友 hellow_world00 提供,参见代码如下:
解法二:
下面这种方法也挺巧妙的,思路是建立长度为k的数组v,只有当v里面所有的数字都是 target 的时候,才能返回 true。我们还需要给数组排个序,由于题目中限制了全是正数,所以数字累加只会增大不会减小,一旦累加超过了 target,这个子集合是无法再变小的,所以就不能加入这个数。实际上相当于贪婪算法,由于题目中数组数字为正的限制,有解的话就可以用贪婪算法得到。用一个变量 idx 表示当前遍历的数字,排序后,从末尾大的数字开始累加,遍历数组v,当前位置加上 nums[idx],如果超过了 target,跳过继续到下一个位置,否则就调用递归,此时的 idx 为 idx-1,表示之前那个数字已经成功加入数组v了,尝试着加下一个数字。如果递归返回 false 了,就将 nums[idx] 从数组v中对应的位置减去,还原状态,然后继续下一个位置。如果某个递归中 idx 等于 -1 了,表明所有的数字已经遍历完了,此时检查数组v中k个数字是否都为 target,是的话返回 true,否则返回 false,参见代码如下:
解法三:
Github 同步地址:
#698
类似题目:
Partition Equal Subset Sum
参考资料:
https://leetcode.com/problems/partition-to-k-equal-sum-subsets/
https://leetcode.com/problems/partition-to-k-equal-sum-subsets/discuss/108730/javacstraightforward-dfs-solution
https://leetcode.com/problems/partition-to-k-equal-sum-subsets/discuss/108751/easy-to-understand-java-solution
LeetCode All in One 题目讲解汇总(持续更新中...)
The text was updated successfully, but these errors were encountered: