416. Partition Equal Subset Sum
题目大意 给定一个数组，求能不能把数组分成两部分使得两个子数组的和相等
解题思路：直接brute force解，数组的每个元素都取二进制0或者1来表示有没有选取，这样时间复杂度太高。会超时
动态规划：dp[i][j]表示能否用数组前i个元素的到和j。退一步就是能否用前i-1个元素得到和 j - num_i 。所以如果 dp[i-1][j - num_i] 成立，那么dp[i][j]也成立。最后就是检查dp[n-1][sum/2]是不是成立。所以如果数组的和为基数的话，那么肯定无解。
动态规划
class Solution(object):
def canPartition(self, nums):
n = len(nums)
s = sum(nums)
if s % 2 != 0:
return False
dp = [0 for _ in range(s + 1)]
dp[0] = 1
for num in nums:
for i in range(s, -1, -1):
if dp[i]:
dp[i+num] = 1
if dp[s/2]:
return True
return False