专栏首页木又AI帮打卡群刷题总结1003——分割等和子集

打卡群刷题总结1003——分割等和子集

题目:416. 分割等和子集

链接:https://leetcode-cn.com/problems/partition-equal-subset-sum

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。 注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200 示例 1: 输入: [1, 5, 11, 5] 输出: true 解释: 数组可以分割成 [1, 5, 5] 和 [11]. 示例 2: 输入: [1, 2, 3, 5] 输出: false 解释: 数组不能分割成两个元素和相等的子集.

解题:

1、dp问题。将数组切分为等和子集,即是求任意个元素的和等于数组和的一半。使用dp数组,第i个元素表示任意个元素的和能否等于i。那么在任意一个dp[i-n](n为nums中任意元素)为True的情况下,dp[i] 为True。

代码

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        target = sum(nums)
        if target % 2 == 1:
            return False
        
        nums.sort()
        target = target // 2
        dp =  [False] * (target + 1)
        dp[0] = True
        for i, n in enumerate(nums):
            for j in range(target, n - 1, -1):
                if dp[j - n] == True:
                    dp[j] = True
        print(dp)
        return dp[-1]

PS:刷了打卡群的题,再刷另一道题,并且总结,确实耗费很多时间。如果时间不够,以后的更新会总结打卡群的题。

PPS:还是得日更呀,总结一下总是好的。

本文分享自微信公众号 - 木又AI帮(gh_eaa31cab4b91),作者:木又

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-10-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 打卡群刷题总结0724——子集

    链接:https://leetcode-cn.com/problems/subsets

    木又AI帮
  • 打卡群刷题总结0930——最大整除子集

    链接:https://leetcode-cn.com/problems/largest-divisible-subset

    木又AI帮
  • 【leetcode刷题】T171-分割等和子集

    https://leetcode-cn.com/problems/partition-equal-subset-sum/

    木又AI帮
  • 打卡群2刷题总结1003——搜索旋转排序数组

    https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

    木又AI帮
  • 打卡群刷题总结0826——组合总和

    链接:https://leetcode-cn.com/problems/combination-sum

    木又AI帮
  • 打卡群刷题总结0827——组合总和 II

    链接:https://leetcode-cn.com/problems/combination-sum-ii

    木又AI帮
  • 打卡群刷题总结1001——组合总和 Ⅳ

    链接:https://leetcode-cn.com/problems/combination-sum-iv

    木又AI帮
  • 打卡群刷题总结0812——路径总和 II

    链接:https://leetcode-cn.com/problems/path-sum-ii

    木又AI帮
  • 打卡群刷题总结0624——四数之和

    1、先将数组排序,接着使用暴力破解,最后两层循环可以使用two sum的方式求和。

    木又AI帮
  • 打卡群刷题总结0722——颜色分类

    链接:https://leetcode-cn.com/problems/sort-colors

    木又AI帮
  • 打卡群刷题总结0928——整数拆分

    链接:https://leetcode-cn.com/problems/integer-break

    木又AI帮
  • 打卡群刷题总结0729——分隔链表

    木又AI帮
  • 打卡群刷题总结0718——最小路径和

    链接:https://leetcode-cn.com/problems/minimum-path-sum

    木又AI帮
  • 打卡群刷题总结0918——乘积最大子数组

    链接:https://leetcode-cn.com/problems/maximum-product-subarray

    木又AI帮
  • 打卡群刷题总结0924——最长上升子序列

    链接:https://leetcode-cn.com/problems/longest-increasing-subsequence

    木又AI帮
  • 打卡群刷题总结0708——字母异位词分组

    链接:https://leetcode-cn.com/problems/group-anagrams

    木又AI帮
  • 打卡群刷题总结0816——三角形最小路径和

    链接:https://leetcode-cn.com/problems/triangle

    木又AI帮
  • 打卡群2刷题总结1004——无重复字符的最长子串

    https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

    木又AI帮
  • 打卡群刷题总结0611——区域和检索-数组不可变

    链接:https://leetcode-cn.com/problems/range-sum-query-immutable

    木又AI帮

扫码关注云+社区

领取腾讯云代金券