Leetcode-416.分割等和子集

2021年6月30日 17点热度 0条评论 来源: TransientYear

文章目录

题目描述

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

注意:

  1. 每个数组中的元素不会超过 100
  2. 数组的大小不会超过 200

示例 1:

输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2:

输入: [1, 2, 3, 5]

输出: false

解释: 数组不能分割成两个元素和相等的子集.

分析

这道题其实可以变成是0-1背包问题,利用动态规划思想做题:

  • 状态表示: F ( n , C ) F(n,C) F(n,C),表示前n个数,是否能找到和为C的数字组合,能为True,不能为False
    • 如果不考虑第n个元素,那么情况等于前n-1个元素的情况即 F ( n − 1 , C ) F(n-1,C) F(n1,C)
    • 如果考虑第n个元素,那么情况等于前n-1个元素的子集和加上第n个元素的和可以组成和C,C-nums[n]表示前n-1个元素可以组成和为C-nums[n],那么加上第n个元素nums[n],和即可C,可以组成子集。
  • 状态转移公式: F ( n , C ) = F ( n − 1 , C )    o r    F ( n − 1 , C − n u m s ( i ) ) F(n,C)=F(n−1,C) ~~or~~ F(n−1,C−nums(i)) F(n,C)=F(n1,C)  or  F(n1,Cnums(i))
  • 边界:0边界为 F a l s e False False

代码

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        sumNums = sum(nums)
        
        if sumNums%2==1:
            return False

        sumOfHalf = sumNums//2


        length = len(nums)
        dp = [[False for i in range(sumOfHalf+1)] for j in range(length+1)]
        for i in range(length+1):
            dp[i][0] = True

        for i in range(1, length+1):
            for j in range(1, int(sumOfHalf)+1):
                dp[i][j] = dp[i-1][j]
                if j>=nums[i-1]:
                    dp[i][j] = dp[i][j] or dp[i-1][j-nums[i-1]]
        
        return dp[length][sumOfHalf]
    原文作者:TransientYear
    原文地址: https://blog.csdn.net/z_feng12489/article/details/103526528
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。