leetcode 416. Partition Equal Subset Sum | 416. 分割等和子集（Java）

你的名字 2022-09-02 11:55 160阅读 0赞

## 题目 ##

[https://leetcode.com/problems/partition-equal-subset-sum/][https_leetcode.com_problems_partition-equal-subset-sum]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

乍一看是背包问题，但不同的是，本题要求结果等于某值，背包要求结果小于某值。

没想出来怎么 dp，附没走下去的思路草稿：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]  
此方法效率比较低，有空的时候看下官方题解吧。

class Solution { 
        public boolean canPartition(int[] nums) { 
            int sum = 0;
            for (int n : nums) { 
                sum += n;
            }
            if (sum % 2 == 1) return false;
            sum /= 2;
    
            Set<Integer> set1 = new HashSet<>();
            Set<Integer> set2 = new HashSet<>();
            Set<Integer> t;
            set1.add(0);
            for (int n : nums) { 
                for (int i : set1) { 
                    if (i + n == sum) return true;
                    set2.add(i);
                    set2.add(n);
                    set2.add(i + n);
                }
                t = set1;
                set1 = set2;
                set2 = t;
            }
            return false;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

[https_leetcode.com_problems_partition-equal-subset-sum]: https://leetcode.com/problems/partition-equal-subset-sum/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/4c6ffcfa503d4ecb9dd2c6b888c2d6e7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20220829/6f6740fdae8b47b8a4b1e068eb8ef33b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/294724d81da445079011bf22b924d20c.png