Leetcode 416. Partition Equal Subset Sum

题目

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.Note:Each of the array element will not exceed 100.The array size will not exceed 200.

Example 1:
Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:
Input: [1, 2, 3, 5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

解析：

这道题目解的方法主要有两种，第一种利用DFS，第二种利用DP，这边只提供了非常简单的dp方法，关于更快的方法还理解的不到位，留到后面二刷再来补充

解法1：DFS（TLE）

class Solution(object):def canPartition(self, nums):""":type nums: List[int]:rtype: bool"""def backtracking(target):for num in nums:if target>=num:target -= numnums.remove(num)if target == 0 or target in nums or backtracking(target):return Truetarget += numnums.append(num)return Falsetotalsum = sum(nums)if totalsum%2 != 0:return Falsen = len(nums)#target = totalsum/2#nums.sort(reverse = True)return backtracking(totalsum/2)

解法2：二维dfs

留待后续补充，参考网址https://blog.csdn.net/fuxuemingzhu/article/details/79787425

解法3：二维dp

dp数组为dp[i][j]，其意义是使用前i个数字的和能不能构成整数j。我们需要把每个位置都进行遍历，同时也要对0~target之间的所有正整数进行遍历
状态转移方程：

dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]]

代码：

class Solution(object):def canPartition(self, nums):""":type nums: List[int]:rtype: bool"""    totalsum = sum(nums)if totalsum%2 != 0:return Falsen = len(nums)target = totalsum/2dp = [[False]*(target+1) for _ in range(n+1)]for i in range(0,n):dp[i][0] = Truefor i in range(0,target):dp[0][i] = Falsefor i in range(1,n+1):for j in range(1,target+1):if j>=nums[i-1]:dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i-1]]else:dp[i][j] = dp[i-1][j]return dp[n][target]

解法4：一维dp

对解法3进行状态压缩，还理解不到位，留待后续补充
参考网址：https://leetcode.com/problems/partition-equal-subset-sum/discuss/446571/Simple-Python-dp-only-4-lines