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