基础题

分割等和子集

416. 分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

思路

要使得两个子集的元素和项等，就是求一个子集元素和为 sum/2，首先想到的是暴力算法，遍历所有可能的子集进行试探，进而想到使用动态规划， sum/2就是背包容量，数组元素就是物品，我们需要寻找的就是背包装了哪些物品后，刚好装满sum/2的容量，而且一个元素只能使用一次，所以此问题可以转换为 0-1 背包问题。

五部曲

1. dp 数组及其下标含义： dp[i][j]代表表使用0..i这几个元素，在背包容量为j时，这些元素和的最大值

2. 迭代公式： dp[i][j] = max(dp[i-1][j], dp[i-1]][j-num[i]] + num[i])

3. dp 数组初始化

4. 遍历顺序

5. 打印 dp 数组