刚看到这个问题我就隐约回忆起了cs170时候学过的subset问题，然后我发现我完全不记得那个东西是怎么做的。【感觉都是套路阿，都拿这种困扰计算机多年的大题叫人面试即兴做】

Dynamic Programming implementation.

Idea: 先要identify子问题。 这个跟简单版DP不太一样，简单的DP 子问题就一个参数，这里两个参数。 1个是子的target sum. 还有一个是子的given array. 

也就是比如说原本我们要判断target sum =100, array size =0--1000 elements.

我们可以拆分成小的问题，假如target只要10， given array 10个数，能不能sum 出这个结果。

最后是identify subproblem之间的进阶关系：

如果target sum i>= set[j-1]， 比input array 只看到j-1这个元素，要大。我们进行判断：

�target sum=i, array size=0...j的答案要嘛完全等于上一轮的结果，要嘛等于等于子问题

subsets[i-set(j-1)[j-1]]的结果。

复习完subset sum问题之后再看这道题就简单很多。（其实也不能说简单很多吧hhh）

最关键的是如何把这道题变成subset sum problem. 我们缺的东西就是target sum。 这个如果花一点时间想就知道target sum 其实就是所有数字加起来除2. 

最tricky的一点就是要判断target sum是否能被2整除。 如果不行，直接不用判断了。