leetcode hot 100 分割等和子集
416. 分割等和子集
已解答
中等
相关标签
相关企业
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
class Solution(object):
def canPartition(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
n = sum(nums)
if n%2 ==0:
t= n/2
f=[True]+[False for i in range(t)]
f = [f]
for i in range(1,len(nums)+1):
rt_list=[]
# print(f)
for j in range(t+1):
if j-nums[i-1]>=0:
rt_list.append(f[i-1][j] or f[i-1][j-nums[i-1]])
else:
rt_list.append(f[i-1][j])
f.append(rt_list)
return f[len(nums)][t]
else:
return False这里我们最重要的是把她理解成一个背包问题，分割连哥哥一个样的，实际就是在里面挑选总和的一半，而且每个数字只能选择一次