LeetCode_Partition Equal Subset Sum

1. 416题，给定某无序数组，判断其是否能被分成总和相等的两个子集。

2. 此问题可转换成：判断其是否能恰好凑出原数组总和的一半，即 0/1 背包问题。那么可以由此引出两个优化点：若想能凑出，则原数组总和必为偶数，且数组内最大元素不能大于原数组总和一半。

3. 此外便是常规的二维数组压缩至一维的dp套路：

   class Solution {
         public boolean canPartition(int[] nums) {
         int sum = 0;int max = 0;for(int num : nums){
         sum += num;max = Math.max(max, num);}if((sum&1) == 1)return false;sum = sum >>> 1;if(max > sum)return false;// if sum become negative, we can correct it;// now it's subset sum problem; boolean[] dp = new boolean[sum+1];dp[0] = true;for(int num : nums){
         for(int i=sum; i>=num; i--){
         dp[i] = dp[i] || dp[i-num];}if(dp[sum])return true;}return dp[sum];}
   }
   

4. 上述代码运行13ms，注意到，转移条件里，dp[i] 的改变是一次性的（必为false->true），且仅依赖于dp[i-num]。故可优化一下：

   for(int num : nums){
         for(int i=sum; i>=num; i--){
         if(dp[i-num])dp[i] = true;}if(dp[sum])return true;
   }
   

5. 优化后运行7ms，位于92.95%。此外，从这里可以看出，这里小循环的本质是将已经变为true的状态进行传播，由此可引出另一种基于位运算（移位或）的做法，不过，考虑到数据类型的长度，有一定局限性。然而，本题100%的1ms解法是记忆化dfs：

   class Solution {
         public boolean canPartition(int[] nums) {
         int sum = 0;int max = 0;for(int num : nums){
         sum += num;max = Math.max(max, num);}if((sum&1) == 1)return false;sum = sum >>> 1;if(max > sum)return false;visited = new boolean[sum+1];// if sum become negative, we can correct it;// now it's subset sum problem; return dfs(nums, sum, 0, 0);}boolean[] visited;private boolean dfs(int[] nums, int sum, int curSum, int i){
         if(i >= nums.length)return false;if(curSum + nums[i] == sum)return true;if(curSum + nums[i] < sum){
         if(!visited[curSum + nums[i]]){
         visited[curSum + nums[i]] = true;return dfs(nums, sum, curSum+nums[i], i+1) ||dfs(nums, sum, curSum, i+1);}}return dfs(nums, sum, curSum, i+1);}
   }
   

6. 记忆化搜索约等于动态规划。只是本题中，每当dp的大循环更新一次，引入新的元素，都要遍历一次小循环，更新所有状态。而对于dfs，引入新的元素后，其对后续选择的影响是可以直接通过curSum反映出来的，并不需要遍历。此外，本题的测试样例都按照降序排列，这又有助于dfs搜索。

参考资料

1. leetcode本题下优质评论1。
2. leetcode本题下优质评论2。