从题目分析很容易想到回溯法，但是会超时。如果不是提示了有动态规划，很难想到用动规求解。
其实即便知道是动规，初见写也不会做（实话），只从题目怎么能想到01背包呢？
还是有几个特征可以让我们联想到的：
- 每个元素只取一次且不放回
- 背包要放入的商品（集合里的元素）重量为元素的数值，价值也为元素的数值
- 有确定的价值：sum/2
如果想到了01背包（以下采用滚动数组求解），直接开启动规五部曲：
1. 确定 dp 数组的含义：
容量为 j 的背包，放入的重量总和是 dp[j]
这里还有个问题，创建 dp 数组时的长度是多少？
因为我们最后求的价值是 nums 数组和的一半，所以这个长度就是整个范围值的一半，即 200*100/2，赋值一个10001即可。
2. 确定递推公式：
因为背包要放入的商品（集合里的元素）重量为元素的数值，价值也为元素的数值，所以很容易套用01背包的原始递推公式得出：
dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i])
3. 初始化：
首先 dp[0] = 0 这是毫无疑问的。
如果题目给的价值都是正整数那么非0下标都初始化为0就可以了，如果题目给的价值有负数，那么非0下标就要初始化为负无穷。
这样才能让 dp 数组在遍历过程中取最大的价值，而不是被初始值覆盖。
4. 确定遍历顺序：
按照正常01背包滚动数组的遍历顺序遍历就可以了，即外层顺序内层逆序遍历:
for (int i = 0; i < nums.length; i++) {
for (int j = target; j >= nums[i]; j--) { // target时sum/2
dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
}
}5. 模拟举例dp数组：这个可以通过debug来查看
给出完整代码：
class Solution {
public boolean canPartition(int[] nums) {
// 容量为j的背包的，放入的重量总和是dp[j]
int[] dp = new int[10001];
int sum = Arrays.stream(nums).sum();
if (sum % 2 == 1) return false;
int target = sum / 2;
for (int i = 0; i < nums.length; i++) {
for (int j = target; j >= nums[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
}
}
if (dp[target] == target) return true;
return false;
}
}
总结一下，这种题目还是做的太少，以至于想不到动态规划。
看到了讨论区的一个回答，感觉说的很好，需要牢记：
问：怎么想到01背包？
答：做多了类似题目就想到了。这是「从序列中选择子序列使得和接近target」系列的题目，一般都是双向dfs或者01背包问题来完成。
同样思路的题目还有 Leetcode1049.最后一块石头的重量 II
