分割等和子集

题目链接

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

注意:

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

示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
 
示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.

题目解析

本题其实可以进行化简,通过观察若要划分两个和相等的子集,说明原本集合的总和 sum_total 不能为奇数。
因此,我们可以将问题简化为从给定列表中选择n个数,使得这n个数的和等于 target = sum_total //2
此外,对于列表中的最大值```max_num``,若有maxnum>targetmax_num>target,则其他元素之和等于sumtotalmaxnum=2targetmaxnum>targetsum_total-max_num = 2 * target - max_num > target,因此,该情况下也直接返回False。
对于,从列表中遍历满足条件的组合问题可以使用递归,也可以化简为”0-1背包问题“,只不过”0-1背包“问题是找出小于target的组合,这里可以进行一些修改。

解题方法

判断数字奇偶性的两种方法

使用%
原理是通过余2后是否有余数,判断数字是否是偶数。例如:

if num%2==0:
    print("{}是偶数".format(num))
else:
    print("{}是奇数".format(num))

使用&(推荐)
按位运算符,通过判断二进制的最后一位,来判断是否为奇数。

if num & 1:
    print("{}是奇数".format(num))
else:
    print("{}是偶数".format(num))
#为了方便记忆,可以写成
if num & 1 == 0:
    print("{}是偶数".format(num))
else:
    print("{}是奇数".format(num))

递归

递归方法较为简单,利用dfs回溯,每次进行判断是否选择当前值,达到组合的效果。

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        sum_total = sum(nums)
        max_num = max(nums)
        # 判断总和是否为奇数
        if sum_total & 1:
            return False
        target = sum_total // 2
        if max_num > target:
            return False
        
        size = len(nums)

        def dfs(cur_sum, i):
            if i >= size or cur_sum > target:
                return False
            if cur_sum == target:
                return True
            # 进行选择
            res = dfs(cur_sum + nums[i], i + 1) or dfs(cur_sum, i + 1)
            return res
        return dfs(0, 0)

复杂度分析:
时间复杂度:O(2N)O(2^N),N为列表数字的个数,将问题化简为每位数字选与不选,最坏情况下将遍历集合所有数字,也可想象为解空间是一棵二叉树,层数为列表数字个数N。
空间复杂度:O(N)O(N),递归所消耗的隐式栈的空间。

记忆化递归

上述解法是不满足时间限制的,也就是说这种解法并不能算上正规解法,因为它原则上还是暴力搜索。但是,我们怎么进行改进呢?
加入记忆化
记忆化的思想就是,对于重复子问题,保存到hash表中,这样我们就降低了重复子问题的运算时间。
改进代码如下:

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        sum_total = sum(nums)
        max_num = max(nums)
        # 判断总和是否为奇数
        if sum_total & 1:
            return False
        target = sum_total // 2
        if max_num > target:
            return False
        
        size = len(nums)
        memory = {}
        def dfs(cur_sum, i):
            if (cur_sum,i) in memory:
                return memory[(cur_sum,i)]
            if i >= size or cur_sum > target:
                return False
            if cur_sum == target:
                return True
            # 进行选择
            res = dfs(cur_sum + nums[i], i + 1) or dfs(cur_sum, i + 1)
            memory[(cur_sum,i)]=res
            return res
        return dfs(0, 0)

动态规划法

该问题可以看做”0-1背包“问题的变体,dp[i][j]的含义是(0-i)是否可以选择某些数使得它们的和为j。那么对于初始dp数组,所有元素为False。

  • 当j=0时,显然不选择数即可满足条件,所以dp[i][0]=True
  • 当nums[i] <= j时, nums[i]可以选取或不选取,两种情况只要有一种为True,dp[i][j]即为True:
    • 如果不选取,dp[i][j]=dp[i1][j]dp[i][j]=dp[i-1][j]
    • 如果选取,dp[i][j]=dp[i1][jnums[i]]dp[i][j]=dp[i-1][j-nums[i]]
  • 当nums[i]>j时,nums[i]不可选取,因此有dp[i][j]=dp[i1][j]dp[i][j]=dp[i-1][j]
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        sum_total = sum(nums)
        max_num = max(nums)
        # 判断总和是否为奇数
        if sum_total & 1:
            return False
        target = sum_total // 2
        if max_num > target:
            return False
        size = len(nums)
        if size <2:
            return False
        # dp初始化
        dp=[[False for _ in range(target+1)] for _ in range(size)]
        for i in range(size):
            dp[i][0]=True
        dp[0][nums[0]]=True
        for i in range(1, size):
            for j in range(1, target+1):
                if nums[i] <= j:
                    dp[i][j] = dp[i-1][j-nums[i]] | dp[i-1][j]
                else:
                    dp[i][j]=dp[i-1][j]
        return dp[size-1][target]

复杂度分析:
时间复杂度:O(n×target)O(n\times target),可以看出如果target很大,dp的时间复杂度将大于递归。
空间复杂度:O(n×target)O(n \times target)

动态规划空间改进

可以观察到,dp数组的更新仅依赖于上一层dp值,因此我们可以进一步压缩空间。将dp数组压缩到一维,每次保存每一层的状态,并且从大到小更新,因为从小到大的更新的话,更新到dp[j]时,dp[j-num]已经是该层已经被修改过的值。

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        sum_total = sum(nums)
        max_num = max(nums)
        # 判断总和是否为奇数
        if sum_total & 1:
            return False
        target = sum_total // 2
        if max_num > target:
            return False
        size = len(nums)
        if size <2:
            return False
        # dp初始化
        dp=[False] * (target+1)
        dp[0]=True
        for i, num in enumerate(nums):
            for j in range(target, num - 1, -1):
                dp[j] |= dp[j - num]
        return dp[target]

参考

https://leetcode-cn.com/problems/partition-equal-subset-sum/solution/fen-ge-deng-he-zi-ji-by-leetcode-solution/
https://leetcode-cn.com/problems/partition-equal-subset-sum/solution/shou-hua-tu-jie-fen-ge-deng-he-zi-ji-dfshui-su-si-/