这段代码的目的是解决 LeetCode 416 问题：分割等和子集，即判断一个只包含正整数的数组，是否能够将其分割成两个子集，使得这两个子集的元素和相等。
算法思想（动态规划 - 背包问题）
该问题本质上是一个经典的动态规划问题，可以转化为“0-1 背包问题”，具体解释如下：
1. 总和判断：
- 首先，我们需要计算数组中所有元素的总和
sum。 - 如果这个总和
sum是 奇数，那我们无法将其分为两个和相等的子集，因为奇数无法均匀分成两个整数。因此，直接返回false。 - 如果
sum是 偶数，则问题转化为：我们能否找到一个子集，使得该子集的和等于sum / 2。如果可以找到这样一个子集，那么剩余的元素自然也会构成另一个子集，它们的和也为sum / 2。
2. 动态规划：
- 动态规划的核心思想是：我们用一个布尔数组
dp来表示从数组中是否可以选出若干元素使得这些元素的和为j。其中dp[j]表示数组中的某些子集是否可以构成和为j的子集。 - 初始化：
dp[0] = true，表示我们可以通过不选择任何元素来构成和为0的子集。 - 遍历数组中的每个元素
num，从后向前更新dp数组。对于每一个num，我们要判断是否能通过之前的选择和这个num构成和为j的子集。
3. 代码执行过程：
- 首先计算数组元素的总和。
- 如果总和是奇数，直接返回
false。 - 然后创建一个目标和
target = sum / 2，这也是我们希望找到的子集的和。 - 初始化一个长度为
target + 1的布尔数组dp，用于记录是否可以通过某些元素构成特定的子集和。 - 对数组中的每个元素
num，从后向前遍历dp数组，更新dp[j]，表示是否可以用之前的元素和当前元素num构成和为j的子集。 - 最后，
dp[target]的值即为我们想要的结果，如果dp[target]为true，则表示可以找到这样的子集，返回true；否则返回false。
动态规划的状态转移方程：
dp[j] = dp[j] || dp[j - num]，即：- 如果在没有当前数字
num的情况下可以构成和为j的子集，那么dp[j]为true。 - 或者，如果在没有当前数字
num的情况下可以构成和为j - num的子集，那么加上当前数字num后也可以构成和为j的子集。
- 如果在没有当前数字
时间复杂度：
- 时间复杂度为 O(n * target)，其中
n是数组中元素的个数，target是总和的一半（即sum / 2）。
总结：
这个问题使用动态规划解决，类似于“背包问题”的思路。通过判断是否可以找到和为 sum / 2 的子集，我们就可以判断数组是否能够被分割成两个和相等的子集。
java solution
class Solution {public boolean canPartition(int[] nums) {//只有nums所有元素和为偶数时，才有可能分割等和子集int sum = 0;for(int num : nums) {sum = sum + num;}if(sum % 2 != 0) {return false;}//如果所有元素和为偶数, 那么我们只要可以找到凑成和为 sum / 2 的子集，就可以返回 trueint target = sum / 2;//创建boolean类型的dp数组, dp[i] 表示子集元素是否可以凑成和为 i// 通过 dp[target] 来判断是否凑成功, 所以创建 target + 1 个存储单元boolean[] dp = new boolean[target + 1]; //创建的boolean数组初始值默认为falsedp[0] = true; //我们可以不选择任何元素来凑成 0//遍历每个数组元素,从后往前更新 dpfor(int num : nums) {for(int j = target; j >= num; j--) {dp[j] = dp[j] || dp[j - num];}}return dp[target];}
}
如果 dp[j] 原本是 true，表示已经能够找到和为 j 的子集，保留 true；
或者，如果 dp[j - num] 为 true，表示可以通过之前的元素组合成和为 j - num 的子集，那么加上当前的 num，就可以组合成和为 j 的子集，所以 dp[j] 也应更新为 true
这部分代码片段，为什么是从后往前更新dp数组？
// 遍历每个数字for (int num : nums) {// 从后向前更新 dp 数组for (int j = target; j >= num; j--) {dp[j] = dp[j] || dp[j - num];}}
这个代码片段中从 后往前 更新 dp 数组是为了防止在更新过程中产生错误的结果。原因与避免重复使用同一个元素有关，这是动态规划中处理“0-1 背包问题”时的常见技巧。
问题背景：
在这个问题中，每个元素只能使用一次。这与完全背包问题不同，后者允许一个元素多次使用。为了确保我们在更新 dp 数组时，使用的每个数字 num 只被处理一次，我们需要从后往前更新 dp 数组。
详细解释：
假设我们从前往后更新 dp 数组（即 for (int j = num; j <= target; j++)）会导致的问题：
- 例如，如果我们有一个数字
num = 5，当前目标和target = 11。 - 当我们从前往后更新时，如果首先更新了
dp[5]，假设原本dp[5] = false，在这次更新中我们设置了dp[5] = true。 - 但是，当我们接着更新
dp[10]时，dp[10]的更新依赖于dp[5]。由于我们刚刚把dp[5]更新为了true，此时dp[10]也会被更新为true。这样导致的问题是我们实际上用了两次num = 5来实现目标和，因为dp[10]是由新更新的dp[5]推导而来的，而这个dp[5]实际上是在同一轮循环中刚刚被更新过的。
因此，从前往后更新会导致我们错误地“多次使用”同一个元素。
为什么从后往前更新可以避免这个问题？
通过从后往前更新，可以确保每个元素 num 在每轮循环中只被使用一次。因为当我们更新 dp[j] 时，dp[j - num] 是基于 上一次循环的结果，而不是当前循环已经更新过的结果。具体原因如下：
- 当我们从
target向num方向遍历时，dp[j]只依赖于dp[j - num]，而dp[j - num]在当前循环之前还没有被更新过，因此不会重复使用同一个元素。
举例说明：
假设我们有数组 nums = [1, 5]，目标和为 6，dp 数组的初始状态如下：
dp = [true, false, false, false, false, false, false]
其中 dp[0] 为 true 表示可以通过不选任何元素实现和为 0。
- 首先处理
num = 1，从后往前更新dp数组：- 更新
dp[6]，不变，因为dp[5]还是false。 - 更新
dp[5]，不变，因为dp[4]还是false。 - 更新
dp[1] = dp[1] || dp[0] = true。更新后：
- 更新
dp = [true, true, false, false, false, false, false]
- 接下来处理
num = 5，从后往前更新dp数组：- 更新
dp[6] = dp[6] || dp[1] = true，因为dp[1]已经是true（由之前的num = 1得到）。 - 更新
dp[5] = dp[5] || dp[0] = true，因为dp[0]是true。
- 更新
最终得到：
dp = [true, true, false, false, false, true, true]
这说明我们可以找到两个子集，分别为 {1, 5}，它们的和都是 6。
总结：
从后往前更新 dp 数组的目的是防止在同一次循环中重复使用同一个元素。这样确保了每个元素在一轮循环中只被考虑一次，从而正确解决问题。
为什么外层循环是遍历nums数组，而不是遍历j？
这段代码的外层循环遍历 nums 数组而不是直接遍历 j，是因为我们需要逐个处理数组中的每个数字，并根据这些数字来逐步更新 dp 数组。它遵循的算法思想是“0-1 背包问题”，每个数字只能使用一次，而不是可以无限制地使用。
具体原因和解释：
1. 动态规划的过程依赖于逐个数字的处理：
- 这个问题的核心是寻找是否存在一个子集，其和等于目标值
target。为了实现这一点，我们必须逐个遍历数组中的每一个元素，检查当前元素num是否能与之前选择的数字组合成新的子集，从而更新是否能够构成特定的和。 - 外层循环遍历
nums数组，表示我们依次将数组中的每个元素加入到子集的选择中，然后根据这些元素更新dp数组，记录我们是否能够构成特定的子集和。
2. 动态规划状态的更新依赖于每个数字：
- 对于每个数字
num，我们需要判断当前这个num能否帮助我们构成新的子集和，即从和为j - num的子集中，加上num，能否构成和为j的子集。这是通过内层循环来完成的。 - 外层循环遍历数组中的每个数字，每次拿到一个新的
num，我们就尝试更新所有可能的子集和（从target到num）。因此，外层循环必须遍历nums数组，以确保每个元素都被考虑一次。
3. 逐步构造子集和：
- 动态规划的过程是一步步地构造所有可能的子集和，并用
dp[j]来记录是否能构成和为j的子集。因此，必须逐个遍历每个num，以确保每个数字都被正确处理，并且能基于前面的状态更新新的状态。
4. 确保每个数字只被使用一次：
- 如果外层循环遍历
j，而不是遍历nums数组，我们就无法确保每个数字num只被使用一次。这是因为，如果直接遍历j，那么在每一轮更新dp数组时，我们可能会使用同一个num多次。 - 通过外层循环遍历
nums，我们保证每次只处理一个数字num，并在内层循环中根据这个num更新dp数组。这符合“0-1 背包问题”的要求：每个元素最多只能使用一次。
举个例子：
假设我们有数组 nums = [1, 5]，目标和为 6，dp 数组初始为：
dp = [true, false, false, false, false, false, false]
此时：
- 外层循环遍历
nums，首先处理num = 1，它会从target开始逐步更新dp数组，确保它和之前的组合是否可以构成新的子集。 - 接下来处理
num = 5，同样从target开始往前更新。
通过这种方式，我们保证每个 num 只被处理一次，避免重复使用同一个元素。
总结：
- 外层循环遍历
nums数组，是为了逐一处理数组中的每个数字，确保每个数字num都能正确参与到子集和的构造过程中。 - 通过外层循环遍历
nums数组，可以有效地控制每个数字num只使用一次，避免重复选择。这符合“0-1 背包问题”的要求，即每个元素只能使用一次。
