剛看到這個(gè)問(wèn)題我就隱約回憶起了cs170時(shí)候?qū)W過(guò)的subset問(wèn)題，然后我發(fā)現(xiàn)我完全不記得那個(gè)東西是怎么做的锰镀⌒址模【感覺(jué)都是套路阿，都拿這種困擾計(jì)算機(jī)多年的大題叫人面試即興做】
Dynamic Programming implementation.
Idea: 先要identify子問(wèn)題技矮。 這個(gè)跟簡(jiǎn)單版DP不太一樣抖誉，簡(jiǎn)單的DP 子問(wèn)題就一個(gè)參數(shù)，這里兩個(gè)參數(shù)衰倦。 1個(gè)是子的target sum. 還有一個(gè)是子的given array.?
也就是比如說(shuō)原本我們要判斷target sum =100, array size =0--1000 elements.
我們可以拆分成小的問(wèn)題袒炉，假如target只要10， given array 10個(gè)數(shù)樊零，能不能sum 出這個(gè)結(jié)果我磁。
最后是identify subproblem之間的進(jìn)階關(guān)系：
如果target sum i>= set[j-1]孽文， 比input array 只看到j(luò)-1這個(gè)元素，要大夺艰。我們進(jìn)行判斷：
?target sum=i, array size=0...j的答案要嘛完全等于上一輪的結(jié)果芋哭，要嘛等于等于子問(wèn)題
subsets[i-set(j-1)[j-1]]的結(jié)果。
復(fù)習(xí)完subset sum問(wèn)題之后再看這道題就簡(jiǎn)單很多郁副。（其實(shí)也不能說(shuō)簡(jiǎn)單很多吧hhh）
最關(guān)鍵的是如何把這道題變成subset sum problem. 我們?nèi)钡臇|西就是target sum减牺。 這個(gè)如果花一點(diǎn)時(shí)間想就知道target sum 其實(shí)就是所有數(shù)字加起來(lái)除2.?
最tricky的一點(diǎn)就是要判斷target sum是否能被2整除。 如果不行存谎，直接不用判斷了拔疚。
