这题标签是简单，但是难度并不简单，难点在于如何将题目转化成为01背包问题。
而01背包问题如果掌握，这道题只要思路转化过来即可解出。

题目给了一个数组nums，要求说是在数组里面找个一个子集，找个子集的和与剩下的元素组成的子集的和相等。
相当于：一个集合N，是否存在一个子集Q，sum{Q} = sum{N-Q}

sum{Q}意思为集合Q中所有元素相加求和和

这个问题可以放大一点，转化为：nums是否存在子集Q，这个Q的所有元素加起来等于一个tar（tar是一个任意的给定的正整数）。
在这个问题中，当tar=sum/2时，就是该题目原本的解答了。（sum为nums中所有元素的和）。

简洁的说法：nums设为集合N，N是否存在子集Q，sum{Q}=tarsum\{Q\}=tarsum{Q}=tar（tar为一个任意的正整数）。
当tar=sum{N}/2tar = sum\{N\}/2tar=sum{N}/2时就是该题目所要求的答案了

f(i,j)f(i,j)f(i,j)中，j是tar，i是划分的子集。

尝试用y总的dp分析方法分析一下：

f(i,j)f(i,j)f(i,j)代表的集合为：所有的nums的子集.

eg. nums{1,3,4}nums\{1,3,4\}nums{1,3,4}的集合为{{1},{3},{4},{1,3},{1,4},{3,4}}\{\{1\}, \{3\}, \{4\}, \{1,3\}, \{1,4\}, \{3,4\}\}{{1},{3},{4},{1,3},{1,4},{3,4}}

属性：这些集合的和中是否有一个等于jjj

集合划分：集合中是否含有nums[i]nums[i]nums[i]这个元素

状态转移:

nums[i]>jnums[i] > jnums[i]>j时
f[i][j]=f[i−1][j]f[i][j] = f[i-1][j]f[i][j]=f[i−1][j]

nums[i] f[i][j]=f[i−1][j−nums[i]∣f[i−1][j]f[i][j] = f[i-1][j-nums[i] \quad | \quad f[i-1][j]f[i][j]=f[i−1][j−nums[i]∣f[i−1][j]

初始化：

当i=1，nums[0]时，f[i−1][j−nums[i]]f[i-1][j-nums[i]]f[i−1][j−nums[i]]所依赖f[i][0]=truef[i][0]=truef[i][0]=true；f[i−1][j]f[i-1][j]f[i−1][j]依赖的是f[0][nums[0]]f[0][nums[0]]f[0][nums[0]]，根据提议可知f[0][nums[0]]=truef[0][nums[0]]=truef[0][nums[0]]=true.因此初始条件为：
f[i][0]=truef[i][0]=truef[i][0]=truef[0][nums[0]]=truef[0][nums[0]]=truef[0][nums[0]]=true

一些前提条件判定的分析就不写了，比如说sum必须为偶数， halfSum > maxNum啥的。

Java代码如下：

class Solution {public boolean canPartition(int[] nums) {int sum = 0, n = nums.length, maxNum = -1;if (n < 2) return false;for(int i : nums) {sum += i;maxNum = Math.max(maxNum,i);}if(sum % 2 != 0) return false;int halfSum = sum / 2;if(maxNum > halfSum) return false;boolean[][] f = new boolean[n][halfSum+1];//初始化//f(i,0)=truefor(int i = 0; i < n; i++) {f[i][0] = true;//这个是朴素写法，可以优化一下，只写f[0][nums[0]] = true;f[i][nums[i]] = true;}for(int i = 1; i < n; i++){for(int j = nums[0]; j <= halfSum; j++){if(j > nums[i]) f[i][j] = f[i-1][j-nums[i]] | f[i-1][j];else f[i][j] = f[i-1][j];}}return f[n-1][halfSum];}
}