Partition Equal Subset Sum Problem in Java

均分整数子集问题 是算法领域一个重要的问题，在算法面试中经常出现。该类问题中最简单的问题是判断一组正整数是否可以被分成两个和相等的子集。

这个问题可以通过多种技术来解决，而 动态规划 是解决此问题最有效的方法之一。

问题陈述

假设我们只有一组正整数，那么问题就来了，是否可以将给定的 数组 分成两个值相等的子集。例如

输入

输出

 
True (The array can be partitioned as [1, 5, 5] and [11])   

关键洞察

求和： 要做到这一点，首先需要计算给定数组中所有数字的总和。在这种情况下，如果总和是奇数，则无法将其分成两个相等的部分或两个相等的子集。

目标和： 这意味着如果总和是偶数，那么我们试图得到的每个子集的目标和是总和的一半。

解决问题的方法

暴力破解法

该方法的工作原理是获取给定数组的所有可能子集，然后检查其中至少一个是否等于总和的一半。

时间复杂度为 O(2^n)

带备忘录的递归

这种方法使用递归来探索可能的子集，同时存储先前计算的结果以避免重复计算。

时间复杂度降低到 O(n×target)，其中 target 等于总和的一半，由于使用了备忘录表，空间复杂度也与 n×target 相同。

动态规划（表格法）

这种最佳方法采用自底向上的动态规划，其中构建一个表来存储可达到的和。

虽然时间复杂度仍为 O(n×target)，但空间复杂度有所降低，因为在此方法中，使用了一维数组而不是二维数组。

文件名：Solution.java

输出

 
true
false   

解释

在处理输入数组时，第一个操作是确定数组中所有数字的总和。如果总和是奇数，则无法将总和分成两个相等的部分，因此返回 false。

也就是说，如果计算出的总和是偶数，则将目标值设置为等于总和的一半。然后，我们声明一个布尔数组 dp，其中 dp[i] 表示是否存在和为 i 的子集。

为了处理 nums 中的每个数字，我们从右到左遍历 dp 数组。这有助于基于是否可以通过包含或排除当前数字来求和 j 来计算 dp[j]。最后，我们检查 dp[target] 是否为 true；如果是，则可以实现求和目标的子集。

结论

均分整数子集问题旨在展示算法设计的重要方面，包括动态规划和子集问题。认识到这个问题不仅可以教会应聘者技术面试知识，还可以教会他们适用于计算机科学各个领域的解决问题的方法。

此处提供的 Java 实现被证明是一个非常可靠的运行时解决方案，可以有效地解决数组分区问题，使得两个分区（一个是一个分区的反向）具有相同的 Σ 值。