分割等和子集

题目链接

示例 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``，若有$max_num>target$，则其他元素之和等于$sum_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(2^N)$，N为列表数字的个数，将问题化简为每位数字选与不选，最坏情况下将遍历集合所有数字，也可想象为解空间是一棵二叉树，层数为列表数字个数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[i-1][j]$
  • 如果选取，$dp[i][j]=dp[i-1][j-nums[i]]$
• 当nums[i]>j时，nums[i]不可选取，因此有$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\times target)$，可以看出如果target很大，dp的时间复杂度将大于递归。
空间复杂度：$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-/