分割等和子集
题目原文
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
注意:
每个数组中的元素不会超过 100
数组的大小不会超过 200
注意:
每个数组中的元素不会超过 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``,若有,则其他元素之和等于,因此,该情况下也直接返回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)
复杂度分析:
时间复杂度:,N为列表数字的个数,将问题化简为每位数字选与不选,最坏情况下将遍历集合所有数字,也可想象为解空间是一棵二叉树,层数为列表数字个数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:
- 如果不选取,
- 如果选取,
- 当nums[i]>j时,nums[i]不可选取,因此有
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]
复杂度分析:
时间复杂度:,可以看出如果target很大,dp的时间复杂度将大于递归。
空间复杂度:
动态规划空间改进
可以观察到,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-/